java - 最多 k 次买卖股票的最大利润 [递归到 DP]

Question

与其他 DP 问题不同，我无法将以下问题分解为重叠的子问题，因此 DP 解决方案对我来说并不直观。

https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/

我发现到处都有自下而上的方法来解决这个问题。我想用自上而下的方法来解决它。与任何其他问题一样，我想首先提出递归解决方案，然后使用 DP 数组来缓存重叠结果。我无法使其重叠，因此无法使 DP 直观。请帮我将其转换为 DP

以下是我的递归解决方案。

private int getMaxProfit(ArrayList<Integer> input, int K) {
    return getMaxProfit(input, 0, 0, 0, K, K, 0);
}

private int getMaxProfit(ArrayList<Integer> input, int i, int buy, int sell, int bk, int sk, int bal) {
    if (i == input.size() || (bk == 0 && sk == 0)) { // k times Buying, selling done or we reached end
        return buy > sell ? 0 : sell - buy;
    }

    /** If Buying for k times done **/
    if (bk == 0) {
        int neutral = getMaxProfit(input, i + 1, buy, sell, bk, sk, bal + 1);
        int maxProfitBySell = getMaxProfit(input, i + 1, buy, sell + input.get(i), bk, sk - 1, bal - 1);
        return Math.max(neutral, maxProfitBySell);
    }
    /** If Selling for k times done **/
    if (sk == 0) {
        int neutral = getMaxProfit(input, i + 1, buy, sell, bk, sk, bal + 1);
        int maxProfitByBuy = getMaxProfit(input, i + 1, buy + input.get(i), sell, bk - 1, sk, bal + 1);
        return Math.max(neutral, maxProfitByBuy);
    }
    /** we need to buy one stock before we sell it **/
    if (bal == 0) {
        return getMaxProfit(input, i + 1, buy + input.get(i), sell, bk - 1, sk, bal + 1);
    }
    int maxProfitByBuy = getMaxProfit(input, i + 1, buy + input.get(i), sell, bk - 1, sk, bal + 1); // buy
    int neutral = getMaxProfit(input, i + 1, buy, sell, bk, sk, bal + 1); // dont buy or sell
    int maxProfitBySell = getMaxProfit(input, i + 1, buy, sell + input.get(i), bk, sk - 1, bal - 1); //sell
    return Math.max(neutral, Math.max(maxProfitByBuy, maxProfitBySell));
}

Answer 1

要转换为自下而上的方法，如果首先自上而下地制定递归方法(意味着调用的参数正在减少)，并且参数状态之间具有明确的关联，则可以更加直观和容易和结果。由于在此问题中，事务是连续的，并且每个事务都由两部分组成，因此实现此目的的一种方法是将 K 加倍并使用其当前奇偶校验来指示事务中的状态。

这里使用 JavaScript 自上而下进行注释，利用问题描述中共享的 Geeks-for-Geeks 链接中的输入示例。 (请注意，此处的“卖出”是在其各自的“买入”之前进行检查的。)

// Odd k means the (k/2)th buy was completed
function f(A, k, i=A.length-1){
  // All transactions were done
  if (k == 0)
    return 0
  // We're at the start of the price list
  // so if we are in the middle of a transaction,
  // force the associated "buy"
  if (i == 0)
    return k & 1 ? -A[0] : 0
  
  // Current k is odd so we have completed a "sell" -
  // choose to record the associated "buy" or skip
  if (k & 1){
    return Math.max(
      -A[i] + f(A, k - 1, i - 1), // buy
      f(A, k, i - 1) // skip
    )
  // Current k is even so we have completed a "buy" or
  // are "at rest" - choose to record a new "sell" or skip
  } else {
    return Math.max(
      A[i] + f(A, k - 1, i - 1), // sell
      f(A, k, i - 1) // skip
    )
  }
}

var inputs = [
  [[10, 22, 5, 75, 65, 80], 2], // 87
  [[12, 14, 17, 10, 14, 13, 12, 15], 3], // 12
  [[100, 30, 15, 10, 8, 25, 80], 3], // 72
  [[90, 80, 70, 60, 50], 1] // 0
]

for (let [A, K] of inputs){
  console.log(`A: ${A}, K: ${K}`)
  console.log(f(A, 2*K)) // call with doubled K
}

现在是自下而上的转换，几乎相同 (O(n2k) = O(nk)):

// Bottom-up
function f(A, k){
  let M = new Array(A.length)
  
  for (let i=0; i<A.length; i++)
    M[i] = new Array(2*k + 1).fill(0)

  // Base case - force buy
  for (let j=1; j<=2*k; j+=2)
    M[0][j] = -A[0]

  for (let i=1; i<A.length; i++){
    for (let j=1; j<=2*k; j++){
      if (j & 1){
        M[i][j] = Math.max(
          -A[i] + M[i-1][j-1], // buy
          M[i - 1][j]
        )
     
      } else {
        M[i][j] = Math.max(
          A[i] + M[i-1][j-1], // sell
          M[i-1][j]
        )
      }
    }
  }

  return M[A.length-1][2*k]
}

var inputs = [
  [[10, 22, 5, 75, 65, 80], 2], // 87
  [[12, 14, 17, 10, 14, 13, 12, 15], 3], // 12
  [[100, 30, 15, 10, 8, 25, 80], 3], // 72
  [[90, 80, 70, 60, 50], 1] // 0
]

for (let [A, K] of inputs){
  console.log(`A: ${A}, K: ${K}`)
  console.log(f(A, K))
}