leetcode 309. Best Time to Buy and Sell Stock with Cooldown
目录
题目描述
第一步，明确并理解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]);}
};