无限供应多面额硬币的找零组合数计算技术问询

嘿，咱们来拆解这个经典的找零计数问题！

问题核心 #

给定$M\geq 1$种面额为$a_1, \ldots, a_M$的硬币，每种硬币随便拿，现在要算出凑出总价值$n\geq 0$的不同方式有多少种。

举个接地气的例子：用1美分（pennies）和5美分（nickels）凑10美分，一共3种玩法：

• 2枚5美分直接凑满
• 1枚5美分+5枚1美分
• 10枚1美分慢慢凑

单一面额的简单情况 #

如果只有一种面额$a_1$的硬币，那事儿就好办多了：

• 要是$n$能被$a_1$整除，那只有1种方式——全用这个面额的硬币就行；
• 要是$n$没法被$a_1$整除，那凑不出来，方式数就是0。

多面额的通用解法：动态规划 #

面对多种硬币时，动态规划是最靠谱的解法，一步步构建每个金额的找零方式数：

步骤拆解 #

1. 定义状态：咱们设dp[i]代表凑出金额i的找零方式总数。
2. 初始化：dp[0] = 1——凑0元只有一种办法：啥硬币都不用。
3. 状态转移：挨个遍历每种硬币面额a_j，然后从a_j到n遍历所有金额i，更新dp[i] += dp[i - a_j]。
   这里的逻辑是：凑i元的方式数，等于原来不用a_j硬币的方式数，加上用至少一枚a_j硬币（也就是先凑出i - a_j元，再添一枚a_j）的方式数。

代码示例（Python） #

def count_coin_combinations(target, coins):
    # 初始化dp数组，dp[0] = 1，其余初始为0
    dp = [0] * (target + 1)
    dp[0] = 1
    
    # 遍历每种硬币
    for coin in coins:
        # 从硬币面额开始遍历到目标金额
        for amount in range(coin, target + 1):
            dp[amount] += dp[amount - coin]
    
    return dp[target]

# 测试咱们开头的例子：凑10美分，硬币是[1,5]
print(count_coin_combinations(10, [1,5]))  # 输出3，完美匹配例子结果

注意事项 #

• 如果硬币列表里有重复面额或者0面额，记得先预处理去掉——0面额没意义，还会让程序陷入无限循环；
• 这个问题本质和整数拆分是一类的，因为硬币的使用顺序不影响方式计数（比如先放1分再放5分，和先放5分再放1分算同一种）。

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