121. 買賣股票的最佳時(shí)機(jī)

題目鏈接
解題思路：
動規(guī)五部曲分析如下：

1.確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][0] 表示第i天持有股票所得最多現(xiàn)金 ，這里可能有同學(xué)疑惑，本題中只能買賣一次，持有股票之后哪還有現(xiàn)金呢？

其實(shí)一開始現(xiàn)金是0，那么加入第i天買入股票現(xiàn)金就是 -prices[i]， 這是一個(gè)負(fù)數(shù)。

dp[i][1] 表示第i天不持有股票所得最多現(xiàn)金

注意這里說的是“持有”，“持有”不代表就是當(dāng)天“買入”！也有可能是昨天就買入了，今天保持持有的狀態(tài)

2.確定遞推公式

如果第i天持有股票即dp[i][0]， 那么可以由兩個(gè)狀態(tài)推出來

• 第i-1天就持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：dp[i - 1][0]
• 第i天買入股票，所得現(xiàn)金就是買入今天的股票后所得現(xiàn)金即：-prices[i]

那么dp[i][0]應(yīng)該選所得現(xiàn)金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]， 也可以由兩個(gè)狀態(tài)推出來

• 第i-1天就不持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：dp[i - 1][1]
• 第i天賣出股票，所得現(xiàn)金就是按照今天股票價(jià)格賣出后所得現(xiàn)金即：prices[i] + dp[i - 1][0]

同樣dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

3.dp數(shù)組如何初始化

由遞推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出

其基礎(chǔ)都是要從dp[0][0]和dp[0][1]推導(dǎo)出來。

那么dp[0][0]表示第0天持有股票，此時(shí)的持有股票就一定是買入股票了，因?yàn)椴豢赡苡星耙惶焱瞥鰜?#xff0c;所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票，不持有股票那么現(xiàn)金就是0，所以dp[0][1] = 0;

4.確定遍歷順序

從遞推公式可以看出dp[i]都是由dp[i - 1]推導(dǎo)出來的，那么一定是從前向后遍歷。

5.舉例推導(dǎo)dp數(shù)組

以示例1，輸入：[7,1,5,3,6,4]為例，dp數(shù)組狀態(tài)如下：
dp[5][1]就是最終結(jié)果。

為什么不是dp[5][0]呢？

因?yàn)楸绢}中不持有股票狀態(tài)所得金錢一定比持有股票狀態(tài)得到的多！

以上分析完畢，C++代碼如下：

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};

---

122.買賣股票的最佳時(shí)機(jī)II

題目鏈接
解題思路：
本題和121. 買賣股票的最佳時(shí)機(jī) 的唯一區(qū)別是本題股票可以買賣多次了（注意只有一只股票，所以再次購買前要出售掉之前的股票）

代碼如下：

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意這里是和121. 買賣股票的最佳時(shí)機(jī)唯一不同的地方。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[len - 1][1];}
};

大家可以本題和121. 買賣股票的最佳時(shí)機(jī)的代碼幾乎一樣，唯一的區(qū)別在：

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

這正是因?yàn)楸绢}的股票可以買賣多次！ 所以買入股票的時(shí)候，可能會有之前買賣的利潤即：dp[i - 1][1]，所以dp[i - 1][1] - prices[i]。