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

##### 问题描述投票：0回答：1

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

``````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 0 0 0 0
1 1 1 1 1
1 1 2 2 3
``````

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

dynamic-programming coin-change
##### 1个回答
0

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

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)。
• 如果到达第一行，我们将返回一个空列表
• 如果我们到达第一列，我们将返回已经找到的内容，其中将包含目标的总和。