目錄

題目描述

第一步，明確并理解dp數組及下標的含義

第二步，分析并理解遞推公式

1.求dp[i][0]

2.求dp[i][1]

3.求dp[i][2]

第三步，理解dp數組如何初始化

第四步，理解遍歷順序

代碼

---

題目描述

這道題與第122題的區別就是賣出股票后的一天不能買股票。仍然用動態規劃解決。這類題目的關鍵是要分析每一天有幾種狀態，用dp數組變量記錄這些狀態。?

第一步，明確并理解dp數組及下標的含義

//dp[i][0]表示從第0天開始一直到第i天結束時，處于持有股票的狀態，此時的最大利潤

//dp[i][1]表示從第0天開始一直到第i天結束時，由于第i天賣出股票此時處于不持有股票的狀態，此時的最大利潤

//dp[i][2]表示從第0天開始一直到第i天結束時，由于第i天之前賣出股票并且第i天沒有賣出股票此時處于不持有股票的狀態，此時的最大利潤

        int n = prices.size();//dp[i][0]表示從第0天開始一直到第i天結束時，處于持有股票的狀態，此時的最大利潤//dp[i][1]表示從第0天開始一直到第i天結束時，由于第i天賣出股票此時處于不持有股票的狀態，此時的最大利潤//dp[i][2]表示從第0天開始一直到第i天結束時，由于第i天之前賣出股票并且第i天沒有賣出股票此時處于不持有股票的狀態，此時的最大利潤vector<vector<int>> dp(n,vector<int>(3,0));

第二步，分析并理解遞推公式

1.求dp[i][0]

//第i天結束時處于持有股票的狀態，有兩種可能的原因：

//一是前一天(第i-1天)結束時就已經處于持有股票的狀態(對應狀態dp[i-1][0]),第i天什么也不做。

//二是第i天買入了股票(需支付prices[i]),第i天能買入股票的前提是第i-1天結束時就已經處于不持有股票的狀態(并且第i-1天沒有賣出股票)(對應狀態dp[i-1][2])。

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

2.求dp[i][1]

//第i天結束時處于不持有股票的狀態并且是因為第i天賣出了股票,第i天能賣出股票的前提是第i-1天結束時處于持有股票的狀態(對應dp[i-1][0])

dp[i][1] = dp[i-1][0] + prices[i];

3.求dp[i][2]

//第i天結束時處于不持有股票的狀態并且第i天沒有賣出股票，有兩種可能的原因：

//一是前一天(第i-1天)賣出了股票導致第i-1天結束時處于不持有股票的狀態(對應狀態dp[i-1][1])。

//二是前一天(第i-1天)的之前賣出了股票，而不是前一天的當天賣出了股票，導致第i-1天結束時處于不持有股票的狀態(對應狀態dp[i-1][2])。

dp[i][2] = max(dp[i-1][1],dp[i-1][2]);

        for(int i = 1;i < n;i++){//第i天結束時處于持有股票的狀態，有兩種可能的原因：//一是前一天(第i-1天)結束時就已經處于持有股票的狀態(對應狀態dp[i-1][0]),第i天什么也不做。//二是第i天買入了股票(需支付prices[i]),第i天能買入股票的前提是第i-1天結束時就已經處于不持有股票的狀態(并且第i-1天沒有賣出股票)(對應狀態dp[i-1][2])。dp[i][0] = max(dp[i-1][0],dp[i-1][2] - prices[i]);//第i天結束時處于不持有股票的狀態并且是因為第i天賣出了股票,第i天能賣出股票的前提是第i-1天結束時處于持有股票的狀態(對應dp[i-1][0])dp[i][1] = dp[i-1][0] + prices[i];//第i天結束時處于不持有股票的狀態并且第i天沒有賣出股票，有兩種可能的原因：//一是前一天(第i-1天)賣出了股票導致第i-1天結束時處于不持有股票的狀態(對應狀態dp[i-1][1])。//二是前一天(第i-1天)的之前賣出了股票，而不是前一天的當天賣出了股票，導致第i-1天結束時處于不持有股票的狀態(對應狀態dp[i-1][2])。dp[i][2] = max(dp[i-1][1],dp[i-1][2]);}

第三步，理解dp數組如何初始化

dp[0][0] = -prices[0];//第0天結束時處于持有股票的狀態，那只能是因為第0天買入了股票(需支付prices[0]),利潤為負prices[0]

dp[0][1] = 0;//第0天結束時處于不持有股票的狀態，并且是因為第0天賣出了股票，可以理解為第0天先買入了股票然后又賣出了，最終利潤是0

dp[0][2] = 0;//第0天結束時處于不持有股票的狀態，并且第0天沒有賣出股票，只能是因為第i天什么也沒做，利潤保持為初始值0

第四步，理解遍歷順序

第i天的狀態依賴于第i-1天的狀態，因此i的遍歷順序應該從小到大。

代碼

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();//dp[i][0]表示從第0天開始一直到第i天結束時，處于持有股票的狀態，此時的最大利潤//dp[i][1]表示從第0天開始一直到第i天結束時，由于第i天賣出股票此時處于不持有股票的狀態，此時的最大利潤//dp[i][2]表示從第0天開始一直到第i天結束時，由于第i天之前賣出股票并且第i天沒有賣出股票此時處于不持有股票的狀態，此時的最大利潤vector<vector<int>> dp(n,vector<int>(3,0));dp[0][0] = -prices[0];//第0天結束時處于持有股票的狀態，那只能是因為第0天買入了股票(需支付prices[0]),利潤為負prices[0]dp[0][1] = 0;//第0天結束時處于不持有股票的狀態，并且是因為第0天賣出了股票，可以理解為第0天先買入了股票然后又賣出了，最終利潤是0dp[0][2] = 0;//第0天結束時處于不持有股票的狀態，并且第0天沒有賣出股票，只能是因為第i天什么也沒做，利潤保持為初始值0for(int i = 1;i < n;i++){//第i天結束時處于持有股票的狀態，有兩種可能的原因：//一是前一天(第i-1天)結束時就已經處于持有股票的狀態(對應狀態dp[i-1][0]),第i天什么也不做。//二是第i天買入了股票(需支付prices[i]),第i天能買入股票的前提是第i-1天結束時就已經處于不持有股票的狀態(并且第i-1天沒有賣出股票)(對應狀態dp[i-1][2])。dp[i][0] = max(dp[i-1][0],dp[i-1][2] - prices[i]);//第i天結束時處于不持有股票的狀態并且是因為第i天賣出了股票,第i天能賣出股票的前提是第i-1天結束時處于持有股票的狀態(對應dp[i-1][0])dp[i][1] = dp[i-1][0] + prices[i];//第i天結束時處于不持有股票的狀態并且第i天沒有賣出股票，有兩種可能的原因：//一是前一天(第i-1天)賣出了股票導致第i-1天結束時處于不持有股票的狀態(對應狀態dp[i-1][1])。//二是前一天(第i-1天)的之前賣出了股票，而不是前一天的當天賣出了股票，導致第i-1天結束時處于不持有股票的狀態(對應狀態dp[i-1][2])。dp[i][2] = max(dp[i-1][1],dp[i-1][2]);}return max(dp[n-1][1],dp[n-1][2]);}
};