【leetcode】309. 最佳买卖股票时机含冷冻期（best-time-to-buy-and-sell-stock-with-cooldown）（DP）[中等]

链接

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

耗时

解题：1.5 h
题解：18 min

题意

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

思路

dp[i] 表示 从 第 0 0 0 天 到 第 i i i 天 可以获得的 最大利润。当后一天的价格大于当天价格时，适合买入。每天都可以卖出买入的股票，那么如果当天卖出的话，最大利润就是所有 {买入卖出的差价+买入前前一天的最大利润} 的最大值。但是，也有可能当天卖出没有前一天获得的利润大。所以 dp[i] = max(当天卖出的最大利润, 前一天的最大利润)。

时间复杂度：最坏情况下是 O ( n 2 ) O(n^2) O(n2)

AC代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        vector<int> dp(n, 0), buy;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < buy.size(); ++j) {
                int prof = prices[i] - prices[buy[j]];
                dp[i] = max(dp[i], prof + (buy[j]-2>=0 ? dp[buy[j]-2] : 0));
            }
            if(i > 0 && dp[i] < dp[i-1])
                dp[i] = dp[i-1];
            if(i < n-1 && prices[i+1] > prices[i]) {
                buy.push_back(i);
            }
        }
        return dp[n-1];
    }
};