[LeetCode] 问题系列 - 买卖股票的问题

188 Best Time to Buy and Sell Stock IV
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

  public int maxProfit(int k, int[] prices) {
        // DP: t(i,j) (0<=i<=K, 0<=j<=price.len)
        int len = prices.length;
        // 对 (k >= len / 2) 的处理很重要
        if (k >= len / 2) return quickSolve(prices); // 暂时不写了
        int[][] t = new int[k + 1][len];
        // 这部分的思路和Best Time III是一样的
        for (int i = 1; i <= k; i++) {
            int cost = -prices[0];
            for (int j = 1; j < len; j++) {
                t[i][j] = Math.max(t[i][j - 1], prices[j] + cost);
                cost =  Math.max(cost, t[i - 1][j - 1] - prices[j]);
            }
        }
        return t[k][len - 1];
    }

t[i][j]表示的是到第j天为止，进行不多于i次的买卖（一买一卖算一次），能有的最大利润。
我们重点讲一下下面这部分代码：

for (int i = 1; i <= k; i++) {
    for (int j = 0; j < len; j++) {
        if (j == 0) {
            t[i][j] = 0;
            cost = -prices[0];
        } else {
            t[i][j] = Math.max(t[i][j - 1], prices[j] + cost);
            cost =  Math.max(cost, t[i - 1][j - 1] - prices[j]);
        }
    }
}

cost表示的是目前（第j天的时候），手上有一支股票还没卖（就是之前有买）。这个值等于两部分取更大（cost是负数，所以max意味着更低的价格买入）：

1. 之前买入了 - cost
2. 今天买入，也就是用之前赚到的利润再投入一部分买一支股 - t[i - 1][j - 1] - prices[j]

t[i][j]也有两部分组成：

1. 到前一天为止，不多于i次操作得到的最大利润（表示今天没有操作）
2. 今天卖了之前买的那一股 - prices[j] + cost