最多买卖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加倍并使用其当前奇偶性来指示事务状态来实现此目的。

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

// 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))
}