硬币面值组合问题python

硬币面值组合问题是计算机科学中的一个典型动态规划问题，通常涉及给定一组不同面额的硬币，找出所有可以组成特定总金额的不同组合。例如，给定有5种面值（1元、5角、1角、5分、1分），如何组成10元钱。

在Python中解决这个问题，我们可以使用回溯法或者递归加记忆化搜索（如使用字典记录已计算过的组合）。以下是简单版的递归解决方案：

def coin_change(coins, amount):
    # 边界条件：如果目标金额为0，返回1，表示存在一种组合
    if amount == 0:
        return 1
    # 如果目标金额大于所有硬币面值，返回0，无法组合
    if amount < 0:
        return 0

    # 创建一个字典用于存储已经计算的结果
    memo = {0: 1}  # 初始化基础情况，总金额为0的情况组合数为1

    # 遍历硬币列表
    for coin in coins:
        # 记录当前组合数
        count = memo.get(amount - coin, 0)
        # 更新总金额为当前金额时的组合数
        memo[amount] += count

    return memo[amount]

# 示例
coins = [1, 2, 5]  # 1元, 2元, 5元硬币
amount = 11  # 目标金额
print(coin_change(coins, amount))  # 输出所有组合总数