找到所有排列以获得给定的总和（硬币找零问题）

Question

我正在尝试解决经典的硬币找零（动态）问题。
为了使用动态方法找到所有独特组合的数量以从无限面额的硬币中获得总和，我使用了以下方法：

/* 
     n - number of coins
     arr[] - coin denominations
     x - total sum
     dp[] - array to store number of combinations at index i.
*/
for (int j = 0; j < n; j++)
     for (int i = 1; i <= x; i++)
          if (arr[j] <= i)
              dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

这给了我所有唯一可能的combinations计数：
例如：

Input:
n=3 x=9
Coins: 2 3 5

Output:
3

到目前为止，一切都很好。但我观察到，只需交换上面代码片段中的循环，我就得到了所有可能的结果permutations。

Input:
n=3 x=9
Coins: 2 3 5

Output:
3

这给了我所有唯一可能的permutations计数：
例如：

Input:
3 9
2 3 5

Output:
8

通过调试和经历每次迭代，我映射了一个形成的模式，但不明白为什么我得到排列背后的原因。
任何人都可以反复向我解释这一点吗？任何帮助将不胜感激。
谢谢

这两个问题都可以在这里找到：

• 排列：硬币组合 1
• 组合：硬币组合 2

Answer 1

dp[]第一个带有硬币外循环的代码更新了在每一轮外循环中用新硬币组成值的方法的数量。因此，在第 k 轮之后，我们的dp[]数组仅填充了硬币的组合k，其余的硬币尚未使用。如果我们将组合本身存储为排序的硬币数组，我们只会看到像1 1 5, 和 5 这样的有序组合，并且 5 永远不会出现在 1 之前。这就是组合的原因。

第 m 轮外循环的第二个代码dp[m]使用所有可能的硬币填充第 m 个单元格。m=7所以我们同时计算1 1 5和1 5 1和5 1 1变体。这就是为什么所有排列都在这里计算的原因。

另外评论：我们可以制作二维数组，其中dp[x][c]包含 sum 的排列数量x，以 coin 结尾a[c]。请注意，在这种情况下，我们必须将排列计数与 sum 连接起来x-a[c]。供参考 - 一维和二维 Python 代码。

def coins1(a, n):   #permutations
    count = [1]+[0]*n
    for x in range(1, n + 1):
        for c in a:
            if (x-c >= 0):
                count[x] += count[x-c]
    return count[n]

def coins11(a, n):   #permutations 2d
    m = len(a)
    count = [[1] + [0]*(m-1)] + [[0]*m for i in range(n)]
    for x in range(1, n + 1):
        for c in range(m):
            if x>=a[c]:
                count[x][c] += sum(count[x-a[c]])
    return sum(count[n])