题目

给定一个int[] prices，以及最多可以进行k轮交易(一轮表示分别买一次卖一次)。
每天可以进行一次交易，问最多能取得多大的利润。链接

解释

这个其实跟买股票系列之二很像，即是在prices.length 这么多个price中选出2k个，看哪种选法利润更大。当2k > prices.length 时，本题就可化归为买股票系列之二(可以选任意个)。

状态转移方程

设f[i][j] 表示在[0, i]中选price，进行到第j次交易能获得的最大利润。

f[i][j] >= f[i-1][j] (1)
f[i][j] >= f[i][j-1] + prices[i]*{1,-1}[j%2] (2)
其中不等式(1)表明我多增加了一个选项，能获得的最大利润肯定不小于少一个选项的情况。
不等式(2)表示我每次用prices[i]去尝试，看能不能比之前获得更大的利润。实际上在交易j处，我们可以尝试prices[j-1,…,i]，但是i之前的我们在之前的步骤中已经尝试过了所以不必重复。
最后需要注意的一点是，选择的位置<=2*k。而如果我们到达第i+1个交易位置，这是我们只能用prices[i]去尝试，没有更多的选择，所以此处

f[i][i+1] = f[i][i] + prices[i]*{1,-1}[i%2]

为了处理边缘情况，我们令f[i][0] = 0，这样当k == 0 时则返回0。

同时当j = 1时:
f[i][j]>= prices[i]*{1,-1}[j%2] = f[i][0] + prices*{1,-1}[j%2]

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int maxProfit(int k, int[] prices) {
    if (k>prices.length/2) return maxProfit2(prices);//买股票系列II
    int[] dp = new int[2*k+1];
    int[] sell = new int[]{1,-1};
    for (int i = 0; i < prices.length;i++){
        for (int j=1; j <= Math.min(2*k,i+1);j++)
            if (j==i+1)
                dp[j] = dp[j-1] + prices[i]*sell[j%2];
            else
                dp[j] = Math.max(dp[j], dp[j-1]+prices[i]*sell[j%2]);
    }
    int max_profit = 0;
    for (int i=0; i<= 2*k; i++){
        max_profit=Math.max(max_profit,dp[i]);
    }
    return max_profit;
}