硬币找零-动态规划-如何从DP表中读取所有解决方案

Question

我见过同一问题的不同解决方案，但似乎没有一个使用我使用的方法。所以在这里我尝试使用 DP 表通过自下而上的动态规划方法来解决经典的硬币找零问题。

    int[][] dp = new int[nums.length+1][target+1];
    for (int i = 0; i <= nums.length; ++i)
        dp[i][0] = 1;

    for (int i = 1; i < dp.length; ++i) {
        for (int j = 1; j < dp[i].length; ++j) {
            if (nums[i-1] <= j)
                dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]];
            else
                dp[i][j] = dp[i-1][j];
        }
    }

上面的代码生成了表格。为了好玩，如果我有：{2,3,5} 个硬币，并且想要兑换 8 个，表格将如下所示：

1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1
1 0 1 1 1 1 2 1 2
1 0 1 1 1 2 2 2 3

对于上述情况，以下方法似乎效果很好：

current <- 4
while (current > 0) do
    i <- current
    j <- 8
    while (j > 0) do
        if (dp[i][j] != dp[i-1][j]) then
            nums[i-1] is part of the current solution
            j <- j-1
        else
            i <- i-1
        end
    end
    current <- current-1
end

通过上面的例子，我们得到以下解决方案：

1) [5,3]
2) [3,3,2]
3) [2,2,2,2]

这太棒了！至少我是这么认为的，直到我尝试：{1,2}，T=4。为此，表格如下所示：

1 0 0 0 0
1 1 1 1 1
1 1 2 2 3

用上面的算法打印所有的解，我只得到：

[2,2]
[1,1,1,1]

这意味着我无法康复[2,1,1]。所以这个问题不是关于如何打印这个问题的不同方法的解决方案，而是关于我如何阅读上面的 DP 表来找到所有解决方案。

Answer 1

好吧，我有一个解决方案，但当然......我可以明白为什么其他类似的答案使用不同的方法来解决这个问题。因此，从上表中生成所有可能答案的算法如下所示：

private List<List<Integer>> readSolutions(int[] nums, int[][] dp, int currentRow, int currentColumn, List<Integer> partialSolution) {
    if (currentRow == 0) {
        return new ArrayList<>();
    }

    if (currentColumn == 0) {
        return new ArrayList<List<Integer>>(Collections.singleton(partialSolution));
    }

    List<List<Integer>> solutions = new ArrayList<>();
    if (dp[currentRow][currentColumn] != dp[currentRow-1][currentColumn]) {
        List<Integer> newSolution = new ArrayList<>(partialSolution);
        newSolution.add(nums[currentRow-1]);
        solutions.addAll(readSolutions(nums, dp, currentRow, currentColumn-nums[currentRow-1], newSolution));
        solutions.addAll(readSolutions(nums, dp, currentRow-1, currentColumn, partialSolution));

        return solutions;
    }

    return readSolutions(nums, dp, currentRow-1, currentColumn, partialSolution);
}

另一方面，逻辑很简单。以上表为例：

  0 1 2 3 4
0 1 0 0 0 0
1 1 1 1 1 1
2 1 1 2 2 3

为了获得单一解决方案，我们从右下角开始。如果该值与我们正上方的值匹配，我们就会向上移动。如果没有，我们向左移动与我们所在行相对应的数量。另一方面，要从上表中生成所有答案...

• 我们处于某个位置 (i,j)
• 如果 (i-1,j) 处的值与 (i,j) 相同，我们递归调用 (i-1,j)
• 如果值不匹配，我们有 2 个选择...
• 我们可以使用当前行对应的数字，递归到(i,j-n)
• 我们可以跳过数字并检查是否可以通过使用对 (i-1,j) 的递归调用来创建 (i,j)。
• 如果到达第一行，我们将返回一个空列表
• 如果我们到达第一列，我们将返回已经找到的内容，其中将包含目标的总和。

看起来很糟糕，但按预期工作。