Coin Chane - 动态规划 - 如何从 DP table 读取所有解决方案

Question

我见过针对同一问题的不同解决方案，但 none 似乎使用了我使用的方法。所以我在这里尝试使用 DP table.

以自下而上的动态规划方法解决经典的硬币找零问题

    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];
        }
    }

以上代码生成table。为了好玩，如果我有：{2,3,5} 个硬币，并想交换 8 个，table 看起来像：

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。为此，table 看起来像：

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 table 来找到所有解决方案。

Answer 1

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

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

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

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

为了得到一个单一的解决方案，我们从右下角开始。如果该值确实与我们正上方的值匹配，我们就会向上移动。如果不是，我们向左移动对应于我们所在行的数量。另一方面，从上面生成所有答案 table...

我们在某个位置 (i,j)
如果 (i-1,j) 的值与 (i,j) 相同，我们将递归调用 (i-1,j)
如果值不匹配，我们有 2 个选择...
我们可以使用当前行对应的数字，递归到(i,j-n)
我们可以跳过数字并检查我们是否可以通过使用对 (i-1,j) 的递归调用来代替创建 (i,j)。
如果我们到达第一行，我们return一个空列表
如果我们到达第一列，我们return我们已经找到的东西，它将有目标的总和。

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

Coin Chane - 动态规划 - 如何从 DP table 读取所有解决方案

Coin Chane - Dynamic Programming - How read all solutions from the DP table

dynamic-programming

coin-change