动态问题中的重叠子问题（硬币找零问题）

Question

我正在努力培养对动态规划问题的良好直觉，但我无法理解问题的特定方面。

我将以leetcode上提供的Coin Change问题为例https://leetcode.com/problems/coin-change/

在许多教程中，都提到了自下而上的方法，例如本教程 - https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/

在这种方法中，我们从最佳解决方案开始，然后针对我们的解决方案构建数组。示例 - 我们找到求和 2 然后 3 等的最佳解决方案。最后，我们将有我们的解决方案。这是我理解的方法。

我在思考另一种使用记忆的递归方法时遇到了麻烦。我已经为该问题编写了回溯方法，但不确定如何对其应用记忆。

public int changeCoins_BT(int[] coins, int target, int min, int num_curr) {

    if(target == 0) {
        return min < num_curr ? min : num_curr;
    } else if(target < 0) return min;
    else if(num_curr > min) return min;

    for(int i=0;i<coins.length;i++) {
        min = changeCoins_BT(coins,target-coins[i],min,num_curr+1);
    }

    return min;
}

Answer 1

在寻找 DP 的递归解决方案之前，请尝试确定所讨论问题的子问题。因为，每个子问题都与父问题相同，并且将应用相同的算法。

让我们以硬币找零为例，其中给定了面额列表 d[] 和总和 S，我们需要找到最小面额数，计算（面额的）总和为 S。如果我们想要定义一个解决方案（方法）来查找计数 int findMinDenom(int[] d, int S)。在这一点上我们不知道它会是什么实现，但我们知道 d 和 S 的问题需要什么参数。

请记住，子问题也有相同的解决方案，但总和较低。因此，我们尝试以 findMinDenom 解决每个子问题的方式实现。这将引导我们找到一个递归解决方案，我们用较低的总和 s.

调用相同的方法

int findMinDenom(int[] d, int S) {
  if (S == 0) {
    // If Sum is zero, then no denomination is required.
    return 0;
  }
  int result = Integer.MAX_VALUE; // Define Integer max
  for ( int i = 0; i < d.length; i++) {
    int s = S - d[i] // Reduced to a sub-problem
    // Handle case where s < 0
    if (s < 0) {
      continue;
    }
    int r = findMinDenom(d, s); // Solution for lower sum, s
    result = Math.min(result, r + 1); // Plus 1 because we have just used one denomination.
  }
  return result;
}

我们刚刚用DP解决了。但是，没有记忆。我们将介绍使用数组来保存结果。因为如果子问题已经解决，我们就不会这样做。如果是，那么只是 return 该子问题的结果。对于总和 0，面额将为零。有 solution[0] = 0 并且我们希望找到问题 S 的解决方案，用编码术语来说就是 solution[S]。因此解数组的大小是 S+1.

// Initialize solution
int[] solution = new int[S+1];
solution[0] = 0; 
for (int i = 1; i <= S; i++)
  solution[i] = -1; // Just to denote that solution is not found yet.

现在，通过我们的递归方法的解决方案。

int findMinDenomMemo(int[] d, int S, int[] solution) {
  if (solution[S] > -1) {
    // Solution exists
    return solution[S];
  }
  int result = Integer.MAX_VALUE; // Define Integer max
  for ( int i = 0; i < d.length; i++) {
    int s = S - d[i] // Reduced to a sub-problem
    // Handle case where s < 0
    if (s < 0) {
      continue;
    }
    int r = findMinDenomMemo(d, s, solution); // Solution for lower sum, s
    result = Math.min(result, r + 1); // Plus 1 because we have just used one denomination.
  }
  // Just now solved for sub problem S. So store it.
  solution[S] = result;
  return result;
}

动态问题中的重叠子问题（硬币找零问题）

Overlapping subproblem in a dynamic problem question (Coin change problem)

algorithm

recursion

logic

dynamic-programming

backtracking