動態規劃理論基礎

動規五部曲：

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

出現結果不正確：

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

1. 最佳買賣股票的時機含冷凍期

參考文檔：代碼隨想錄

分析：
加入冷凍期的概念，如果當前賣出了會有一天的冷凍期，這一天不能買入股票，所以節點的狀態增加為 持有 當場賣出 冷凍期 和 賣出狀態 四種。賣出狀態是說明可以持有股票了。
遞推公式：

dp[i][0] = max(dp[i-1][0], max(dp[i-1][2]-prices[i], dp[i-1][3]-prices[i]));
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = dp[i-1][1];
dp[i][3] = max(dp[i-1][3], dp[i-1][2]);

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {//比較重要的是狀態的細分vector<vector<int>> dp(prices.size(), vector<int>(4, 0));dp[0][0] = -prices[0];//持有dp[0][1] = 0;//當天賣出dp[0][2] = 0;//冷凍期dp[0][3] = 0;//賣出狀態for(int i = 1; i < prices.size(); i++){dp[i][0] = max(dp[i-1][0], max(dp[i-1][2]-prices[i], dp[i-1][3]-prices[i]));dp[i][1] = dp[i-1][0] + prices[i];dp[i][2] = dp[i-1][1];dp[i][3] = max(dp[i-1][3], dp[i-1][2]);}return max(max(dp[prices.size()-1][0],dp[prices.size()-1][1]),max(dp[prices.size()-1][2], dp[prices.size()-1][3]));}
};

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] - fee);

代碼：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {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][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);}return max(0,max(dp[prices.size()-1][1], dp[prices.size()-1][0]));}
};