原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv

解法1:

动态规划
承接123题 相当于120-124 这一类股票问题的最通用姐

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
    f[i][j] 表示第i天 持有股票状态为k时的最大现金
    f[i][0] 表示不操作
    f[i][k = 奇数] 表示此时为持有状态
    f[i][k = 偶数] 表示此时为不持有状态
 */
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        // 这里k次买卖 那么对应的所能有的持有状态未k*2次
        k = k * 2;
        int [][] f = new int[n][k + 1];
        // 初始值
        for(int i = 1; i <=k ; i++){
            // 持有状态
            if(i % 2 == 1){
                f[0][i] = -prices[0];
            }else{
                f[0][i] = 0;
            }
        }


        for(int i = 1 ; i < n ; i++){
            f[i][0] = f[i - 1][0];
            for(int j = 1 ; j <=k ; j++ ){
                // 为持有状态 那么只能从上一个未持有状态转移而来 即只能买入 或不操作
                if(j % 2 == 1){                   
                    f[i][j] = Math.max(f[i - 1][j],f[i - 1][j - 1] - prices[i]);
                }else{
                    // 未不持有状态 那么只能从上一个持有状态转移而来 即只能卖出 或不操作
                    f[i][j] = Math.max(f[i - 1][j],f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ans = 0;
        for(int i = 0 ; i <= k ; i += 2){
            // 卖出的值 才会是最大的
            ans = Math.max(ans,f[n - 1][i]);    
        }

        return ans;
    }
}