leetcode-309-线性DP-最佳买卖股票时机含冷冻期

发表于 | 分类于

题目

1.png

解法

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 n = prices.size();
        if(prices.empty() || n == 1) return 0;

        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        int dp_pre_0 = 0;
        for(int i = 1; i < n; ++i){
            int temp = dp_i_0;
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i]);
            dp_pre_0 = temp;
        } 

        return dp_i_0;
    }
};