给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
动态规划
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(3));
dp[0][0] = -prices[0];
for(int i = 1; i < n; i++){
//持有股票
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]);
//不持有股票且处于冷冻期
dp[i][1] = dp[i-1][0] + prices[i];
//不持有股票但不处于冷冻期
dp[i][2] = max(dp[i-1][1], dp[i-1][2]);
}
return max(dp[n-1][1], dp[n-1][2]);
}
};
时间复杂度：O(n)，其中 n 为数组 prices 的长度。
空间复杂度：O(n)。我们需要 3n 的空间存储动态规划中的所有状态，对应的空间复杂度为 O(n)。
我们定义三种情况：
f[i][0]: 手上持有股票的最大收益
f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
首先我们来找这三种情况的状态转换方程。
dp[i][0]代表的是持有股票，也就是第i天结束后是持有股票的。那么如何在第i天结束后持有股票呢？它可以选择不操作，当前一天持有股票，那么第i天结束后依旧持有股票。或者是在第i天他买了股票，那么这就说明了第i-1天结束不处于冷冻期并且没有股票，对应代码dp[i-1][2] - prices[i]。
dp[i][1]是不持有股票且处于冷冻期，如何才能让在第i天结束的时候处于冷冻期呢？只有在第i天进行了卖的操作，那么第i-1天结束的时候，我们肯定是持有股票的，所以有dp[i][1] = dp[i-1][0] + prices[i];。
dp[i][2]是不持有股票但不处于冷冻期，说明我们没有进行买入或者卖出的操作，不然在第i天结束后会持有股票或者处于冷冻期。那么我们不进行操作的话，前一天可以是进行了卖操作然后是冷冻期持续到第i天结束后冷冻期结束，也可以是是前一天也没有进行任何操作，可以从以上两种状态转移而来。 dp[i][2] = max(dp[i-1][1], dp[i-1][2]);。
由于最后我们股票需要卖出才能获得最大收益，所以我们只要取dp[n-1][1], dp[n-1][2]两者的最大值即可。
空间优化
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()){
return 0;
}
int n = prices.size();
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for(int i = 1; i < n; i++){
int new_f0 = max(f0, f2 - prices[i]);
int new_f1 = f0 + prices[i];
int new_f2 = max(f1, f2);
f0 = new_f0;
f1 = new_f1;
f2 = new_f2;
}
return max(f1, f2);
}
};
时间复杂度：O(n)，其中 n 为数组 prices 的长度。
空间复杂度：使用空间优化，空间复杂度可以优化至 O(1)。
我们可以发现，动态规划中状态方程的转移都来自于前一个i-1状态，那么我们可以使用三个变量来记录三种情况的前一种状态，实现空间优化。
标签：力扣,f2,309,int,股票,状态机,prices,冷冻,dp From： https://blog.csdn.net/sjsjs11/article/details/142930787