dp
冷冻期的处理：如果前一天卖出股票，这一天就不能卖，如果前一天没卖，这一天就能卖或者不卖。
对于目前的持股状态，根据卖出和不卖出，持有和不持有组合，共有四种情况：
- 我现在有股票，并且当天没卖出
- 我现在有股票，并且当天卖出了 (违背事实，舍去)
- 我现在没股票，并且当天没卖出
- 我现在没股票，并且当天卖出了
对于1
由于我现在有并且当天没卖出，所以当天的值就是前一天1情况或者前一天没股票但是买入了，也就是3+今天买入后(冷冻期)
对于3
由于我现在没有而且当天也没有，说明我之前就没有，今天也不能买过来，所以我今天的收益就是3和4之中的最大值
对于4
由于我现在没有并且当天卖出了，则今天就不能买入了，所以前一天不能卖出，所以值就是前一天1的情况加上今天卖出的收益。
以上三种状态同步进行，最后最大值会在3，4之间获得到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(3));
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
for(int i = 1; i < prices.size(); ++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][2]);
dp[i][2] = dp[i - 1][0] + prices[i];
}
return max(dp.back()[1], dp.back()[2]);
}
};
|
发现只用到了前一天的数据，所以可以把S(n)优化为O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int dp[3]{-prices[0], 0, 0};
for(int i = 1; i < prices.size(); ++i)
{
auto tmp = dp[2];
dp[2] = dp[0] + prices[i];
dp[0] = max(dp[0], dp[1] - prices[i]);
dp[1] = max(dp[1], tmp);
}
return max(dp[1], dp[2]);
}
};
|
review
根据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int m = prices.size();
if(m == 1)
return 0;
vector<int> have(m);
vector<int> notHave(m);
have[0] = -prices[0];
notHave[0] = 0;
have[1] = max(-prices[1], -prices[0]);
notHave[1] = max(0, -prices[0] + prices[1]);
for(int i = 2; i < m; ++i)
{
have[i] = max(notHave[i - 2] - prices[i], have[i - 1]);
notHave[i] = max(have[i - 1] + prices[i], notHave[i - 1]);
}
return notHave.back();
}
};
|
优化空间后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int m = prices.size();
int have[2]{ 0, -prices[0] };
int notHave[2]{ 0, 0 };
for(int i = 1; i < m; ++i)
{
have[0] = max(notHave[0] - prices[i], have[1]);
notHave[0] = max(have[1] + prices[i], notHave[1]);
swap(have[0], have[1]);
swap(notHave[0], notHave[1]);
}
return notHave[1];
}
};
|