计算不限使用次数的不同面额纸币凑成指定金额的方案数

问题描述 #

给定目标金额n，以及若干种不同面额的纸币，每种纸币供应充足可重复使用，请计算凑出金额n的不同组合方案总数，组合不考虑纸币排列顺序。

示例 #

当目标金额n=3，可用纸币面额c=[3,1,2]时，共有3种符合要求的组合：(1,1,1)、(1,2)、(3)。

输入格式 #

• 第一行输入两个整数n和m，n为目标金额，m为纸币面额种类数
• 第二行输入长度为m的数组c，每个元素对应一种纸币的面额

约束条件 #

• 1 ≤ n ≤ 10000
• 1 ≤ m ≤ 10
• 1 ≤ c[i] ≤ 100

输出格式 #

输出一个整数，代表符合要求的组合方案总数。

样例说明（目标金额为4时） #

若面额包含1、2、3，有效方案为(1,1,1,1)、(1,1,2)、(2,2)、(1,3)，共4种。

解法思路 #

这是典型的完全背包求组合数问题，为了避免重复计数（比如1+2和2+1算同一种组合），我们按面额顺序逐个处理，每次仅考虑是否使用当前面额的纸币，保证组合内的面额按固定顺序出现即可。
动态规划规则如下：

1. 定义dp数组，dp[i]表示凑出金额i的方案总数
2. 初始状态dp[0] = 1，凑出0元只有不选任何纸币1种方案
3. 遍历每个面额coin：
   • 遍历金额从coin到n，更新规则：dp[j] += dp[j - coin]
4. 最终dp[n]就是所求的方案总数

参考代码（Python） #

n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 1
for coin in c:
    for j in range(coin, n + 1):
        dp[j] += dp[j - coin]
print(dp[n])

内容的提问来源于stack exchange，提问作者Yogesh Singh