网站集约化建设较好的城市,企业建设有限公司,怎么看网站开发语言信息,保利集团网页设计作业Leetcode: 309 最佳买卖股票时机含冷冻期
这道题比上面状态更多#xff0c;是因为卖出股票后#xff0c;你无法在第二天买入股票 (即冷冻期为1天)。
状态
状态一#xff1a;持有股票状态#xff08;今天买入股票#xff0c;或者是之前就买入了股票然后没有操作#xf…Leetcode: 309 最佳买卖股票时机含冷冻期
这道题比上面状态更多是因为卖出股票后你无法在第二天买入股票 (即冷冻期为1天)。
状态
状态一持有股票状态今天买入股票或者是之前就买入了股票然后没有操作一直持有
不持有股票状态这里就有两种卖出股票状态
状态二保持卖出股票的状态两天前就卖出了股票度过一天冷冻期。或者是前一天就是卖出股票状态一直没操作
状态三今天卖出股票
状态四今天为冷冻期状态但冷冻期状态不可持续只有一天状态4包含在状态2中
递推公式
这样递推公式就会比较复杂
1、买入股票状态状态一即dp[i][0]有两个具体操作
操作一前一天就是持有股票状态状态一dp[i][0] dp[i - 1][0]
操作二今天买入了有两种情况
前一天是冷冻期状态四dp[i - 1][3] - prices[i]
前一天是保持卖出股票的状态状态二dp[i - 1][1] - prices[i]
那么dp[i][0] max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);
2、保持卖出股票状态状态二即dp[i][1]有两个具体操作
操作一前一天就是状态二
操作二前一天是冷冻期状态四
dp[i][1] max(dp[i - 1][1], dp[i - 1][3]);
3、今天就卖出股票状态状态三即dp[i][2] 只有一个操作
昨天一定是持有股票状态状态一今天卖出
即dp[i][2] dp[i - 1][0] prices[i];
4、冷冻期状态状态四即dp[i][3]只有一个操作
昨天卖出了股票状态三
dp[i][3] dp[i - 1][2];
最后结果是取 状态二状态三和状态四的最大值。
弄清楚这些关系之后代码就很好写了。
时间复杂度O(n)
空间复杂度O(n)
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(len, vectorint(4, 0));dp[0][0] -prices[0];for(int i 1; i len; i){dp[i][0] max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - 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[len-1][1],max(dp[len-1][2],dp[len-1][3]));}
};
Leetcode: 714 买卖股票的最佳时机含手续费
这题可以视为122 买卖股票的最佳时机II的变种因为增加了手续费这样我们只需要在卖出这只股票的时候减去手续费就好了因此所有的代码保持不变只需要更新卖出股票的时候的dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee);就可以了。
时间复杂度O(n)
空间复杂度O(n)
代码如下
class Solution {
public:int maxProfit(vectorint prices, int fee) {int len prices.size();vectorvectorint dp(len, vectorint(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]); dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee);}return dp[len - 1][1];}
};
总结
这段时间跟着代码随想录完成了下述的股票问题受益匪浅。
代码随想录 做这种类型的题目一定要注意状态的划分和状态的变化。
1、分析状态和状态变化的关系只有这些清楚了才能正确解题找到递推公式。需要重点掌握这些状态函数的写法。
2、注意初始化初始化的数值设置很重要不然容易出错。
3、最后输出往往是取最大的。
4、递推顺序一般是从前到后。
