leetcode-123-线性DP-买卖股票的最佳时机III

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 动态规划
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(prices.empty() || n == 1) return 0;
		
        // dp[i][k][0]=x,表示今天没有持有股票,当前最大利润为x,当前最多进行k次交易
        // dp[i][k][1]=x,表示今天持有股票,当前最大利润为x,当前最多进行k次交易
        int max_k = 2;
        int dp[n][max_k+1][2];
        ::memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; ++i){
            for(int k = max_k; k >= 1; --k){
                if(i == 0){
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                // 状态转移
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
           
        } 

        return dp[n-1][max_k][0];
    }
};