网站如何选择服务器,网络认证登录页面,小程序和公众号有什么区别,广东网站推广公司2023.8.22 本题是买卖股票系列 冷冻期。 由于引入了冷冻期#xff0c;并且这个冷冻期是在卖出股票才会出现#xff0c;因此我dp数组设置了四种状态#xff1a;
状态一#xff1a;持有股票。状态二#xff1a;不持有股票#xff1a; 之前就卖了#xff0c;所以今天不处…2023.8.22 本题是买卖股票系列 冷冻期。 由于引入了冷冻期并且这个冷冻期是在卖出股票才会出现因此我dp数组设置了四种状态
状态一持有股票。状态二不持有股票 之前就卖了所以今天不处于冷冻期。状态三不持有股票今天卖。状态四不持有股票昨天卖的所以今天处于冷冻期。 下面分别分析四种状态
持有股票①早就有了dp[i-1][0] ②今天刚买昨天可能是状态二或者状态四不可能是状态三因为今天可以买股票所以不处于冷冻期所以昨天不可能卖股票。即dp[i-1][1]-prices[i] 或者 dp[i-1][3]-prices[i] 。 不持有股票之前就卖了今天不处于冷冻期①昨天的之前就已经卖了即dp[i-1][1]。 ②昨天的昨天卖的即昨天处于冷冻期今天不处于冷冻期即dp[i-1][3]。不持有股票今天卖 没什么好说的昨天持有股票的钱今天股票的股价即dp[i-1][0] prices[i]不持有股票昨天卖今天处于冷冻期已经知道是昨天卖的了即dp[i-1][2]。 最后结果取不持有股票的三种情况的最大值即可。 代码如下
class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(),vectorint(4));//初始化dp[0][0] -prices[0];dp[0][1] dp[0][2] dp[0][3] 0;//状态一持有股票。//状态二不持有股票 之前就卖了所以今天不处于冷冻期。//状态三不持有股票今天卖。//状态四不持有股票昨天卖的所以今天处于冷冻期。for(int i1; iprices.size(); i){dp[i][0] max(dp[i-1][0] , max(dp[i-1][1]-prices[i] , dp[i-1][3]-prices[i]));dp[i][1] max(dp[i-1][1] , dp[i-1][3]);dp[i][2] dp[i-1][0] prices[i];dp[i][3] dp[i-1][2];}return max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));}
}; 附上我的草稿以供参考
