動態規劃理論基礎

動規五部曲：

1. 確定dp數組 下標及dp[i] 的含義。
2. 遞推公式：比如斐波那契數列 dp[i] = dp[i-1] + dp[i-2]。
3. 初始化dp數組。
4. 確定遍歷順序：從前到后or其他。
5. 打印。

出現結果不正確：

1. 打印dp日志和自己想的一樣：遞推公式、初始化或者遍歷順序出錯。
2. 打印dp日志和自己想的不一樣：代碼實現細節出現問題。

1. 買賣股票的最佳時機

參考文檔：代碼隨想錄

分析：
買賣只有一次
dp五部曲：

1. dp[i]含義：dp[i][0]表示持有i手里的現金，dp[i][1]表示不持有i手里的現金。
2. 遞推公式：dp[i][0] = max(dp[i-1][0], 0 - prices[i]); dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
3. 初始化：dp[0][0] = -prices[0]; dp[0][1] = 0;
4. 遍歷順序：從小到大。

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {//dp[i][0]:持有i股手里的錢//dp[i][1]:不持有i股手里的錢vector<vector<int>> dp(prices.size(), vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < prices.size(); i++){//第一次寫的是：dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])//但是股票只能買一次，所以當前的持有是 前一個的持有 和 現在買一個 的最大值dp[i][0] = max(dp[i-1][0], -prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);}return max(dp[prices.size()-1][0], dp[prices.size()-1][1]);}
};

2. 買賣股票的最佳時機Ⅱ

參考文檔：代碼隨想錄

分析：
買賣次數是不限的，之前有用貪心做過，這次用動態規劃。
dp五部曲：

1. dp[i]含義：dp[i][0]表示持有i手里的現金，dp[i][1]表示不持有i手里的現金。
2. 遞推公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]); dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
3. 初始化：dp[0][0] = -prices[0]; dp[0][1] = 0;
4. 遍歷順序：從小到大。

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {//dp[i][0]:i股持有手里的現金，i-1股也持有，i-1股不持有i股重新買入（設計多次買入和一次手中只有一股股票）//dp[i][1]:i股不持有手里的現金:i-1股也不持有，現金不變，i-1股持有i不持有賣出i-1買入i股vector<vector<int>> dp(prices.size(), vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < prices.size(); i++){dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);//i-1股持有，i股不持有，i股拋出，收益prices[i]， dp[i-1][0]+prices[i]dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);}return max(dp[prices.size()-1][0], dp[prices.size()-1][1]);}
};