Python程序：找出用给定硬币表示 n 元的方案数

随着计算机科学的发展，越来越多的问题可以用程序的方法来解决。今天我们要来解决一个有趣的问题：给定几种硬币和一个数额 n，如何找出用这些硬币表示 n 元的方案数？

问题描述

假设我们有以下几种硬币：

现在我们要用以上硬币来表示 10 元，有几种不同的方案？

显然，我们可以通过列举法来得到所有方案：

• 10个1元硬币
• 5个2元硬币
• 3个2元硬币和2个1元硬币
• 2个2元硬币和3个1元硬币
• 2个5元硬币
• 1个5元硬币和2个2元硬币
• 1个5元硬币、1个2元硬币和3个1元硬币
• 1个5元硬币、2个1元硬币和2个2元硬币
• 1个5元硬币、4个1元硬币

一共有 9 种方案。但是如果我们要计算更大的数额，如 100 元，列举法就不再适用了。

解决方案

这时候，我们需要用到一个叫做动态规划的方法，用程序来解决这个问题。动态规划是一个用于解决具有最优子结构的问题的算法。在动态规划中，我们将复杂的问题分解为更小的子问题，并在详尽解决每个小问题的同时存储其解以用于更大问题的求解。

现在，我们用 Python 来实现这个算法：

def count_change(denominations, total):
    n = len(denominations)
    dp = [[0 for _ in range(total+1)] for _ in range(n+1)]

    for i in range(n+1):
        dp[i][0] = 1

    for i in range(1, n+1):
        for j in range(1, total+1):
            if denominations[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-denominations[i-1]]

    return dp[n][total]

函数 count_change 的第一个参数是一个列表，表示硬币的面值；第二个参数是一个整数，表示要找出来的总额。

在函数内部，我们首先声明了一个二维数组 dp，用于存储每个子问题的解。数组 dp[i][j] 表示用前 i 种硬币表示总额为 j 时的方案数。

最后我们返回 dp[n][total]，表示用前 n 种硬币表示总额为 total 的方案数。

接下来，我们再来分析一下代码实现。这段代码使用的是经典的动态规划算法，它需要维护一个二维数组，其中 dp[i][j] 表示用前 i 种硬币表示总额为 j 的方案数。状态转移方程如下：

• 如果第 i 种硬币的面额大于 j，则不能选这种硬币，此时方案数等于用前 i-1 种硬币表示总额为 j 的方案数，即 dp[i][j] = dp[i-1][j]。
• 如果第 i 种硬币的面额小于等于 j，则既可以选这种硬币，也可以不选这种硬币。如果选了这种硬币，那么总额为 j，就减去这种硬币的面额后，剩下的部分就可以用前 i 种硬币表示了，所以方案数是 dp[i][j-denominations[i-1]]。如果不选这种硬币，那么方案数就是用前 i-1 种硬币表示总额为 j 的方案数，即 dp[i-1][j]。所以综合起来，转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-denominations[i-1]]。

算法的时间复杂度为 O(n \times total)，其中 n 是硬币种类的数量。

现在，让我们用这个函数来计算一下前面的例子：用 1 元、2 元、5 元硬币表示 10 元的方案数。

denominations = [1, 2, 5]
total = 10
print(count_change(denominations, total))

输出为 9，即所求结果。

结论

动态规划算法是一种常用的，可以高效解决问题的算法。在本文中，我们用 Python 实现了一个动态规划算法，来求解用给定硬币表示 n 元的方案数。使用动态规划算法，时间复杂度可以控制在 O(n \times total)，可以高效地解决大规模的问题。