Leetcode - Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

[balabala] 此题参照 网友博客的解法http://www.cnblogs.com/grandyang/p/4295761.html。需要维护两个dp数组，分别是local[i][j] 和global[i][j]，前者表示到第i天为止至多完成j次交易且最后一笔交易于第i天完成的最大收益，是一个局部最优值，后者表示到第i天为止至多完成j次交易获取的最大值, 为全局最优值。global[i][j] = max(global[i - 1][j], local[i][j]), 这个递推式比较好理解，是按照第 i 天是否参与交易分类讨论的，local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff).

对于这个解法一度半懂不懂，为什么需要两个dp数组呢？local[][]数组的递推公式如何理解？ 在理解的过程中发现可以这样去理解那些不理解的事物（说得有些绕）：去掉看看效果，正确的解法里每个变量都是有其不可替换的作用的。假设我们只用一个dp数组，dp[i][j]含义同global[i][j]，表示到第i天至多完成j次交易能获取的最大利润，自然地，可以按照第 i 天是否参与最后一笔交易分类讨论，于是递推公式dp[i][j] = max(dp[i - 1][j], max(dp[k][j - 1] + maxProfitBetween(k + 1, i)) ), 式中第二项表示 第i天参与交易的情况，看到仅有dp[][]数组的情况下写起来是多么复杂。于是理解了local[][]数组的好处，使算法复杂度由O(n^3)变为O(n^2)(对比Palindrome Partition II 的降维思路，目前还没看出两种降维思路的想通之处)。local[i][j]是如何递推的呢？ 它的作用是记录到第 i 天至多完成 j 次交易的最大利润且第 i 天完成最后一笔交易，这最后一笔交易卖出点是day i, 买入点可以是0 - i的任意一天，分三种情况讨论：
1） 在i - 1天之前买入：这种情况下可将最后一笔交易以day[i-1]为分割点分解为两笔交易来计算，第一笔是在day[k](k < i -1)买入，day[i -1]卖出，对应于local[i - 1][j], 第二笔是day[i - 1]买入，day[i]卖出，火力为prices[i] - prices[i - 1], 于是这种情况下local[i][j] = local[i-1][j] + prices[i] - prices[i - 1]
2） 在第 i - 1天买入：local[i][j]= global[i - 1][j - 1] + prices[i] - prices[i - 1]
3) 在第 i 天买入: local[i][j]= global[i - 1][j - 1] + 0
合并起来，local[i][j] = local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff), 其中diff = prices[i] - prices[i - 1]

第三个实现yb君的思路，另一角度看问题~

public class Solution {
    // Method 3: space: O(N * k), time: O(N * k)
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int N = prices.length;
        if (N <= k - 1)
            return maxProfitWithoutLimit(prices);
        int M = 2 * k;
        // dp[i][j]: on day i (1, 2... N), max profit after transaction j done
        // transaction j means buy j / 2 + j % 2 times, sell j / 2 times
        int[][] dp = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= i && j <= M; j++) {
                if (j % 2 == 1) {// buy
                    dp[i][j] = dp[i - 1][j - 1] - prices[i - 1];
                    
                } else { // sell
                    dp[i][j] = dp[i - 1][j - 1] + prices[i - 1];
                }
                if (i - 1 >= j)
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
            }
        }
        int max = 0;
        for (int j = 2; j <= M; j += 2) {
            max = Math.max(max, dp[N][j]);
        }
        return max;
    }
    // Method 2space: O(k), time: O(N * k)
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int days = prices.length;
        if (k >= days)
            return maxProfit(prices);
        // local[j] 表示到当日至多完成j次交易，并且最后一笔交易在当日完成的最大收益
        int[] local = new int[k + 1]; 
        // global[j] 表示到当日至多完成j次交易的最大收益
        int[] global = new int[k + 1];
        for (int i = 1; i < days; i++) {
            for (int j = k; j > 0; j--) { // 逆序以利用前一天的结果
                int diff = prices[i] - prices[i - 1];
                local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
                global[j] = Math.max(global[j], local[j]);
            }
        }
        return global[k];
    }
    
    // Method 1: space: O(N * k), time: O(N * k)
    public int maxProfit1(int k, int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int days = prices.length;
        if (k >= days)
            return maxProfit(prices);
        // local[i][j] 表示到第i天至多完成j次交易，并且最后一笔交易在第i天完成的最大收益
        int[][] local = new int[days][k + 1]; 
        // global[i][j] 表示到第i天至多完成j次交易的最大收益
        int[][] global = new int[days][k + 1];
        for (int i = 1; i < days; i++) {
            local[i][0] = 0;
            global[i][0] = 0;
            for (int j = 1; j <= k; j++) {
                int diff = prices[i] - prices[i - 1];
                local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(diff, 0), local[i - 1][j] + diff);
                global[i][j] = Math.max(global[i - 1][j], local[i][j]);
            }
        }
        return global[days - 1][k];
    }
    
    private int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int days = prices.length;
        int profit = 0;
        int delta = 0;
        for (int i = 1; i < days; i++) {
            delta = prices[i] - prices[i - 1];
            profit += delta > 0 ? delta : 0;
        }
        return profit;
    }
}

评论

1 楼 qb_2008 2015-05-05  

带进去简单例子分析一下，就知道代码为什么要这样做了。比如k = 1, prices[] = {1, 4, 3, 7}.
这个问题看成K条装配线上的N个装配站问题或许更容易理解。
N是天数，在每天你可以处于2*k+1种交易状态，让
dp[i][j]为第i天，买入j/2+j%2次，卖出j/2次的最大盈利。
dp[0][0] = 0;
for (int i = 1; i <= N; ++i) {
  for (int j = 1; j <= 2 * k && j <= i; ++i) {
    if (j % 2 == 1) {
      // only can buy.
      dp[i][j] = dp[i - 1][j - 1] - prices[i - 1];
      if (i - 1 >= j) {  // or keep previous value.
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
      }
    } else {
      // only can sell.
      ...
    }
  }
}