excel服务器做网站,百度h5收费吗,在线制作海报免费,商城网站建设缺点问题来源
题目来源链接见下方#xff1a; https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
问题简述#xff1a;
假如有一个 i 个元素的数组#xff0c;数组的每个元素表示了第 i 天某只股票的价格#xff0c;设计一种算法来…问题来源
题目来源链接见下方 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
问题简述
假如有一个 i 个元素的数组数组的每个元素表示了第 i 天某只股票的价格设计一种算法来找到利润最大的买卖方式。设计的算法必须遵守以下两条约束条件
在一天当中只能进行“买”“卖”或者“什么都不干”中的一种操作在“卖”掉股票之后必须“什么都不干”一天
举个例子
prices [1, 2, 3, 0, 2]
maxProfit 3
transactions [buy, sell, cooldown, buy, sell]解题思路
首先申明一下这个思路并不是我想出来的只是在LeetCode上看到有人这样解觉得这个思路很不错所以写下来作为分享和记录。 从题目中可以看出不管哪一天都只能是 buy 或者 sell 或者 cooldown(rest) 三种状态中的一种而根据题目的约束条件我们可以画出下图所示的状态图
图1状态描述图由此图我们可以得到
s0[i] max(s0[i - 1], s2[i - 1])
s1[i] max(s0[i - 1] - prices[i], s1[i - 1])
s2[i] s1[i - 1] prices[i]其中s0s1s2分别表示三种状态下的最大利润值。 值得注意的是这里的s0s1和s2不是单纯的buysell rest而应该是
s0 —— sell后rest或者rest后rest
s1 —— rest后的buy或者buy后的rest
s2 —— rest后的sell同时可以注意到的是每次的状态 i 都只与前一次的状态 i - 1有关也就是说我们可以把空间复杂度从O(n)降到O(1)。
解题代码
好了话不多说下面是时间复杂度为O(n)空间复杂度为O(1)的DP代码
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 1)return 0;int s0 0;int s1 -prices[0];int s2 INT_MIN;for (int i 1; i prices.size(); i){int pre0 s0;int pre1 s1;int pre2 s2;s0 max(pre0, pre2);s1 max(pre0 - prices[i], pre1);s2 pre1 prices[i];}//最大利润不可能出现在buy而未sell的时候所以不考虑s1return max(s0, s2);}
};结束语
利用动态规划解题的难点在于要搞清楚有哪些状态每个状态是怎么来的之后就是把状态用代码写出来了。 如有错误还请指正~
