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

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

这个代码可以帮我计算所有可能的独特组合数量：
例如：

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

Output:
3

目前为止，一切顺利。但是我观察到，仅仅通过交换上述片段中的循环，就可以得到所有可能的排列。

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

这个代码给出了所有唯一可能的“排列”数量：
例如：

Input:
3 9
2 3 5

Output:
8

通过调试并逐次迭代，我绘制出了一种形成的模式，但不理解为什么会得到排列组合。
有人可以逐步解释一下吗？任何帮助将不胜感激。
谢谢。
这两个问题都可以在以下链接中找到：

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

- Dhyey Shah

Answer 1

第一段代码使用外部循环通过硬币更新组成值为dp[]的方法的数量，每次外部循环后一个新硬币将会更新dp[]数组。因此，在第k轮之后，dp[]数组将只被填充了前k个硬币的组合，并且其余的硬币尚未使用。如果我们为已排序的硬币数组存储这些组合本身，我们将只看到像1 1 5这样的有序组合，而5永远不会排在1之前。这就是为什么需要计算组合。

第二段代码在外部循环的第m轮中使用所有可能的硬币填充第m个单元格dp[m]。因此，对于m=7，我们计算1 1 5和1 5 1以及5 1 1这三种变体。这就是为什么在此处计算所有排列的原因。

---

另外作为注释：我们可以创建2D数组，其中dp[x][c]包含以硬币a[c]结尾、总和为x的排列数量。请注意，在这种情况下，我们必须加入总和为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])

- MBo

---

非常感谢！只有一个后续的疑问。我已经为组合问题创建了2D数组，然后将其优化为1D数组。但是在对排列进行相同操作时，我不知道要在每行中放什么到2D数组中？对于排列，是否也可以使用2D数组版本？ - Dhyey Shah