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
動(dòng)態(tài)規(guī)劃法
有一類問題，可以被拆分成一系列的小問題，而這些小問題之間是有聯(lián)系的，下一個(gè)小問題的答案依賴于上一個(gè)小問題的結(jié)果，依此類推到最原始的第0個(gè)初始小問題。
對(duì)于這一類問題的這種解決方法，叫做動(dòng)態(tài)規(guī)劃法。
1. 最大子數(shù)組和 Maximum Subarray - Leetcode 53
思路：
將問題轉(zhuǎn)化為，求一個(gè)數(shù)組d，里面的第i個(gè)元素表示，以nums[i] 結(jié)尾的子數(shù)列，和最大的那個(gè)值。
得到數(shù)組d后，遍歷d，找到里面最大的值，就代表所有子數(shù)組中，最大的那個(gè)和。
2. 買賣股票 Best Time to Buy and Sell Stock - Leetcode 121
思路：
這道題可以用其他更直觀的解法。
不過如果要嘗試用動(dòng)態(tài)規(guī)劃，可以這么想：
這個(gè)問題，其實(shí)就是求，對(duì)于某一天，如果要在當(dāng)天賣，那么找到之前每天價(jià)格的最小值。再假如當(dāng)天要賣，能知道最大收益為多少。最后對(duì)于每一天賣的最大收益，比較出最大的值，就是最大收益了。
那么，這個(gè)問題就轉(zhuǎn)化為，求一個(gè)數(shù)組d，里面的第i個(gè)元素表示，prices 0 到i （包含i），最小的那個(gè)prices元素。
得到數(shù)組d之后，同時(shí)遍歷d和prices數(shù)組，計(jì)算prices[i] - d[i]，找到最大的那個(gè)差值，就是要計(jì)算的最大收益。
3. 買賣股票，有冷靜期 Best Time to Buy and Sell Stock with Cooldown - Leetcode 309
思路：
建立一個(gè)中間數(shù)組，元素 i 表示截至第 i 天為止的最大收益。那么第 i 天與第 i-1 天怎么建立聯(lián)系呢？需要根據(jù)第 i-1 天是否持有股票，再進(jìn)行計(jì)算。
第 i-1 天要么持有股票，要么不持有股票，也就是有兩個(gè)狀態(tài)，那么就需要兩個(gè)中間數(shù)組，或者一個(gè)二維數(shù)組dp[length][2].
dp[i][0] 表示第 i 天收盤時(shí)不持有股票，截至第 i 天為止，最大的收益。
dp[i][1] 表示第 i 天收盤時(shí)持有股票，截至第 i 天為止，最大的收益。
怎么推導(dǎo)出dp[i][0]呢？第 i 天收盤時(shí)不持有股票，有兩種情況：第 i-1 天本來就有股票， 然后第 i 天賣出了股票；或者第 i-1 天本來就沒有股票。也就是：
dp[i][0] = Max( dp[i-1][1] - prices[i], dp[i-1][0] )
怎么推導(dǎo)dp[i][1] 呢？ 第 i 天收盤時(shí)持有股票，有兩種情況：第 i 天買入股票；或者第 i-1天本來就有股票。也就是：
dp[i][1] = Max( dp[i - 2][0] + prices[i], dp[i - 1][1] )
既然列出了公式，那么代碼就顯而易見了。
4. 強(qiáng)盜搶劫 House Robber - Leetcode 198
思路：
二維數(shù)組 dp[length][2]
dp[i][0] 表示第 i 戶人家沒有被搶，此時(shí)劫到的最多錢財(cái)。
dp[i][1] 表示第 i 戶人家被搶了，此時(shí)劫到的最多錢財(cá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. 強(qiáng)盜搶劫2 House Robber II - Leetcode 213
思路：
第0家和第n-1家相鄰，形成一個(gè)圈。
那么分情況討論。構(gòu)建一個(gè)中間數(shù)組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家一定不會(huì)被搶):
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]
