java - 查找所有排列以获得给定的总和(硬币变化问题)

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 轮之后我们有 dp[]数组填充了 k 的组合仅硬币，其余硬币还没用 .如果我们为已排序的硬币数组存储组合本身，我们将只看到像 1 1 5 这样的有序组合。 , 5 永远不会在 1 之前。这就是组合的原因。
第 m 轮外循环的第二个代码填充第 m 个单元格 dp[m]使用所有可能的硬币。所以我们计算 m=7两者 1 1 5和 1 5 1和 5 1 1变种。这就是为什么这里计算所有排列的原因。

另外评论:我们可以制作二维数组，其中dp[x][c]包含总和 x 的排列数, 以硬币结尾 a[c] .请注意，在这种情况下，我们必须将排列计数与总和 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])