Leetcode - 动态规划法 [持续更新]

53. Maximum Subarray --- Easy
121. Best Time to Buy and Sell Stock --- Easy
309. Best Time to Buy and Sell Stock with Cooldown --- Medium
198. House Robber --- Medium
213. House Robber II --- Medium

动态规划法

有一类问题，可以被拆分成一系列的小问题，而这些小问题之间是有联系的，下一个小问题的答案依赖于上一个小问题的结果，依此类推到最原始的第0个初始小问题。
对于这一类问题的这种解决方法，叫做动态规划法。

1. 最大子数组和 Maximum Subarray - Leetcode 53

Leetcode 53

思路：
将问题转化为，求一个数组d，里面的第i个元素表示，以nums[i] 结尾的子数列，和最大的那个值。
得到数组d后，遍历d，找到里面最大的值，就代表所有子数组中，最大的那个和。

2. 买卖股票 Best Time to Buy and Sell Stock - Leetcode 121

Leetcode 121

思路：
这道题可以用其他更直观的解法。

不过如果要尝试用动态规划，可以这么想：
这个问题，其实就是求，对于某一天，如果要在当天卖，那么找到之前每天价格的最小值。再假如当天要卖，能知道最大收益为多少。最后对于每一天卖的最大收益，比较出最大的值，就是最大收益了。
那么，这个问题就转化为，求一个数组d，里面的第i个元素表示，prices 0 到i （包含i），最小的那个prices元素。
得到数组d之后，同时遍历d和prices数组，计算prices[i] - d[i]，找到最大的那个差值，就是要计算的最大收益。

3. 买卖股票，有冷静期 Best Time to Buy and Sell Stock with Cooldown - Leetcode 309

Leetcode 309

思路：
建立一个中间数组，元素 i 表示截至第 i 天为止的最大收益。那么第 i 天与第 i-1 天怎么建立联系呢？需要根据第 i-1 天是否持有股票，再进行计算。
第 i-1 天要么持有股票，要么不持有股票，也就是有两个状态，那么就需要两个中间数组，或者一个二维数组dp[length][2].

dp[i][0] 表示第 i 天收盘时不持有股票，截至第 i 天为止，最大的收益。
dp[i][1] 表示第 i 天收盘时持有股票，截至第 i 天为止，最大的收益。

怎么推导出dp[i][0]呢？第 i 天收盘时不持有股票，有两种情况：第 i-1 天本来就有股票， 然后第 i 天卖出了股票；或者第 i-1 天本来就没有股票。也就是：
dp[i][0] = Max( dp[i-1][1] - prices[i], dp[i-1][0] )

怎么推导dp[i][1] 呢？ 第 i 天收盘时持有股票，有两种情况：第 i 天买入股票；或者第 i-1天本来就有股票。也就是：
dp[i][1] = Max( dp[i - 2][0] + prices[i], dp[i - 1][1] )

既然列出了公式，那么代码就显而易见了。

4. 强盗抢劫 House Robber - Leetcode 198

Leetcode 198

思路：
二维数组 dp[length][2]
dp[i][0] 表示第 i 户人家没有被抢，此时劫到的最多钱财。
dp[i][1] 表示第 i 户人家被抢了，此时劫到的最多钱财。

dp[i][0] = Max( dp[i - 1][0], dp[i - 1][1] );
dp[i][1] = dp[i - 1][0] + nums[i];

dp[0][0] = 0;
dp[0][1] = nums[0];

5. 强盗抢劫2 House Robber II - Leetcode 213

Leetcode 213

思路：
第0家和第n-1家相邻，形成一个圈。
那么分情况讨论。构建一个中间数组dp[n][2]，存放.
第0家没有被抢：
dp[0][0] = 0,
dp[1][0] = Max(dp[0][0], dp[0][1]),
...,
dp[i][0]= Max(dp[i-1][0], dp[i-1][1])

dp[0][1] = 0,
dp[1][1] = dp[0][0] + nums[1],
...,
dp[i][1] = dp[i-1][0] + nums[i]

第0家被抢(第n-1家一定不会被抢):
dp[0][0] = 0,
dp[1][0] = Max(dp[0][0], dp[0][1]),
...,
dp[i][0] = Max(dp[i-1][0], dp[i-1][1])

dp[0][1] = num[0],
dp[1][1] = dp[0][1],
...,
dp[i][1] = dp[i-1][0] + nums[i]