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

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.

for (int i = 1; i <= x; i++)
    for (int j = 0; j < n; j++)
        if (arr[j] <= i)
            dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

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

Input:
3 9
2 3 5

Output:
8

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

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

排列：Coin Combinations 1
组合：Coin Combinations 2

Answer 1

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

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

补充说明：我们可以制作二维数组，其中 dp[x][c] 包含总和 x 的排列数，以硬币 a[c] 结尾。请注意，在这种情况下，我们必须将排列计数与总和 x-a[c] 连接起来。供参考 - 1d 和 2d 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])

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

Finding all permutations to get the given sum (Coin change problem)

java

puzzle

algorithm

dynamic-programming

coin-change