1.题目

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv

2.思路

（1）动态规划
LeetCode股票问题的算法框架可参考团灭 LeetCode 股票买卖问题。

3.代码实现（Java）

//思路1————动态规划
public int maxProfit(int maxK, int[] prices) {
    int length = prices.length;
    if (length == 0) {
        return 0;
    }
    /*
        本题中 k 的最大值可以达到 10^9，不过这是毫无意义的
        因为 length 天最多只能进行⌊length/2⌋笔交易（一次买入和一次卖出算一笔交易）
    */
    maxK = Math.min(maxK, length / 2);
    /*
        定义dp数组dp[i][k][2]（0≤i≤length，0≤k≤maxK），其中
        dp[i][k][0]:在最大交易次数为k的情况下，第i天手中没有股票时的最大利润
        dp[i][k][1]:在最大交易次数为k的情况下，第i天手中持有股票时的最大利润
        该问题共有i*maxK*2种状态
    */
    int[][][] dp = new int[length][maxK + 1][2];
    //k=0
    for (int i = 0; i < length; i++) {
        dp[i][0][1] = Integer.MIN_VALUE;
        dp[i][0][0] = 0;
    }
    for (int i = 0; i < length; i++) {
        for (int k = maxK; k >= 1; k--) {
            //处理i=0的情况
            if (i - 1 == -1) {
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i];
                continue;
            }
            /*
                第i天结束时的有以下两种情况：
                (1) 手里没有股票
                    dp[i - 1][k][0]:与前一天一样，手中没有股票
                    dp[i-1][k][1]+prices[i]:卖掉前一天手中持有的股票，获得的收益为prices[i]
                (2) 手里持有一支股票
                    dp[i - 1][k][1]:保留前一天手中持有的股票
                    dp[i - 1][k - 1][0] - prices[i]:买入当天的股票，减少的收益为prices[i]，需要注意的是，
                        由于第i天需要买入一次，即要消耗一次交易次数，所以到第i-1天为止的最大交易次数为k-1
            */
            dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
            dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
        }
    }
    //dp[length-1][maxK][0]:在最大交易次数为maxK的情况下，最后一天手中没有股票时的最大利润
    return dp[length - 1][maxK][0];
}