Coin Chane-动态编程-如何从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,11]。因此，这个问题不是关于如何打印不同方法的解决方案，而是我如何阅读上面的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(
• 如果值不匹配，我们有两个选择
• 我们可以使用当前行对应的数字，并递归为(i，j-n(
• 我们可以跳过这个数字，通过使用对(i-1，j(的递归调用来检查是否可以创建(i，j(
• 如果到达第一行，则返回一个空列表
• 如果我们到达第一列，我们将返回已经找到的内容，该内容将具有target的和

看起来很糟糕，但效果如预期。