零钱兑换问题（非常详细，附带源码）
零钱兑换问题又叫凑零钱问题，给定不同面值、数量不限的纸币，要求计算拼凑指定的金额最少需要多少张纸币。
举个简单的例子，有 1、7、10 这 3 种面值的纸币，每种纸币的数量不限，要求计算拼凑总面值 15 最少需要多少张纸币。拼凑出总面值 15 的方案有 4 种，分别是：
其中，第 3 个方案（7+7+1）拼凑的总面值是 15，并且使用的纸币数量最少。
零钱兑换问题可以用动态规划算法解决，接下来给大家详细讲解具体的实现思路。
假设用 f(n) 表示凑齐面值 n 所需纸币的最少数量，面值 15 的拼凑方案有 3 种，分别是：
以上 3 种选择方案中，所需纸张数量最少的就是最优的拼凑方案。而想要比较它们，需要先求出 f(14)、f(8)、f(5) 的值。
f(4)、f(7)、f(13) 还可以继续拆分，它们最终会和 f(0)、f(1)、f(2) 产生关联，而 f(0)、f(1)、f(2) 的值是很容易计算的。在得知 f(0)、f(1)、f(2) 等简单问题的结果后，就可以轻松推算出 f(3)~f(14) 的值，进而推算出 f(15) 的值。
因此，零钱兑换问题的解决思路是：从 f(0) 开始，依次计算 f(1)、f(2)......f(n-1)、f(n) 的值，最终的 f(n) 就是凑齐面值 n 所需纸币的最少数量。
计算 f(0) ~ f(n)，它们每一个的值都和 3 种面值纸币的取舍有关系。为了方便读者理解，特意制作了下面的表格：
在不选择任何纸币的情况下，f(1)~f(15) 的值用 ∞（无穷大）表示，f(0) 的值是 0。
1) 考虑选择面值为 1 的纸币，f(1)~f(15) 的计算过程是：
更新表 1 中各个拼凑方案对应的值，如表 2 所示：
2) 考虑选择面值为 7 的纸币，f(1)~f(15) 的计算过程是：
更新表 2 中 f(7)~f(15) 对应的值，如表 3 所示：
3) 考虑选择面值为 10 的纸币，f(1)~f(15) 的计算过程是：
对于 f(14) 和 f(15) 来说，选择面值为 10 的纸币并没有先前的拼凑方案好，所以只更新表 3 中 f(10)~f(13) 对应的值，如表 4 所示：
最终，f(15) 对应的值是 3，表明拼凑出总面值 15 最少需要 3 张纸币。
下面是动态规划解决零钱兑换问题的 C 语言程序：
下面是动态规划解决零钱兑换问题的 Java 程序：
下面是动态规划解决零钱兑换问题的 Python 程序：
运行程序，输出结果为：
举个简单的例子，有 1、7、10 这 3 种面值的纸币，每种纸币的数量不限，要求计算拼凑总面值 15 最少需要多少张纸币。拼凑出总面值 15 的方案有 4 种，分别是：
- 15 张面值为 1 的纸币；
- 1 张面值为 7 的纸币和 8 张面值为 1 的纸币，一共需要 9 张；
- 2 张面值为 7 的纸币和 1 张面值为 1 的纸币，一共需要 3 张；
- 1 张面值为 10 的纸币和 5 张面值为 1 的纸币，一共需要 6 张。
其中，第 3 个方案（7+7+1）拼凑的总面值是 15，并且使用的纸币数量最少。
零钱兑换问题可以用动态规划算法解决，接下来给大家详细讲解具体的实现思路。
动态规划解决零钱兑换问题
接下来仍以“有 1、7、10 这 3 种面值的纸币，计算拼凑总面值 15 最少需要多少张纸币”为例，带大家梳理动态规划思想解决此类问题的过程。假设用 f(n) 表示凑齐面值 n 所需纸币的最少数量，面值 15 的拼凑方案有 3 种，分别是：
- f(15) = f(14) +1：选择一张面值为 1 的纸币，f(14) 表示拼凑出面值 14 所需要的最少的纸币数量；
- f(15) = f(8) + 1：选择一张面值为 7 的纸币，f(8) 表示拼凑出面值 8 所需要的最少的纸币数量；
- f(15) = f(5) + 1：选择一张面值为10 的纸币，f(5) 表示拼凑出面值 5 所需要的最少的纸币数量。
以上 3 种选择方案中，所需纸张数量最少的就是最优的拼凑方案。而想要比较它们，需要先求出 f(14)、f(8)、f(5) 的值。
f(5) = f(4)+1：选择一张面值为 1 的纸币，再加上 f(4) 的值。
f(8) = f(7) + 1：选择一张面值为 1 的纸币，再加上 f(7) 的值。
f(8) = f(1) +1：选择一张面值为 7 的纸币，再加上 f(1) 的值。
f(14) = f(13)+1：选择一张面值为 1 的纸币，再加上 f(13) 的值。
f(14) = f(7) + 1：选择一张面值为 7 的纸币，再加上 f(7) 的值。
f(14) = f(4) +1：选择一张面值为 10 的纸币，再加上 f(4) 的值。
f(4)、f(7)、f(13) 还可以继续拆分，它们最终会和 f(0)、f(1)、f(2) 产生关联，而 f(0)、f(1)、f(2) 的值是很容易计算的。在得知 f(0)、f(1)、f(2) 等简单问题的结果后，就可以轻松推算出 f(3)~f(14) 的值，进而推算出 f(15) 的值。
因此，零钱兑换问题的解决思路是：从 f(0) 开始，依次计算 f(1)、f(2)......f(n-1)、f(n) 的值，最终的 f(n) 就是凑齐面值 n 所需纸币的最少数量。
计算 f(0) ~ f(n)，它们每一个的值都和 3 种面值纸币的取舍有关系。为了方便读者理解，特意制作了下面的表格：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 不选择任何纸币 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
在不选择任何纸币的情况下，f(1)~f(15) 的值用 ∞（无穷大）表示，f(0) 的值是 0。
1) 考虑选择面值为 1 的纸币，f(1)~f(15) 的计算过程是：
- f(1)：选择一张面值为 1 的纸币，那么 f(1) 的值可以用 1+f(0) 表示，1 指的是一张面值为 1 的纸币，f(0) 指的是拼凑金额 0 所需纸币的最少数量。1+f(0) = 1，比 f(1) 的当前值 ∞ 小，表明 1+f(0) 的拼凑方案更佳；
- f(2)： 选择一张面值为 1 的纸币，那么 f(2) 的值可以用 1+f(1) 表示。1+f(1) = 2，比 f(2) 的当前值 ∞ 小，表明 1+f(1) 的拼凑方案更佳；
- f(3)： 选择一张面值为 1 的纸币，那么 f(3) 的值可以用 1+f(2) 表示。1+f(2) = 3，比 f(3) 的当前值 ∞ 小，表明 1+f(2) 的拼凑方案更佳；
- ......
- f(15)：选择一张面值为 1 的纸币，那么 f(15) 的值可以用 1+f(14) 表示。1+f(14) = 15，比 f(15) 的当前值 ∞ 小，表明 1+f(14) 的拼凑方案更佳。
更新表 1 中各个拼凑方案对应的值，如表 2 所示：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 面值为 1 的纸币 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
2) 考虑选择面值为 7 的纸币，f(1)~f(15) 的计算过程是：
- f(1)~f(6)：无法选择面值为 7 个纸币；
- f(7)： 选择一张面值为 7 的纸币，那么 f(7) 的值可以用 1+f(0) 表示，1 指的是一张面值为 7 的纸币，f(0) 指的是拼凑金额 0 所需纸币的最少数量。1+f(0) = 1，比 f(7) 的当前值 7 小，表明 1+f(0) 的拼凑方案更佳；
- f(8)： 选择一张面值为 7 的纸币，那么 f(8) 的值可以用 1+f(1) 表示。1+f(1) = 2，比 f(8) 的当前值 8 小，表明 1+f(1) 的拼凑方案更佳；
- f(9)： 选择一张面值为 7 的纸币，那么 f(9) 的值可以用 1+f(2) 表示。1+f(2) = 3，比 f(9) 的当前值 9 小，表明 1+f(2) 的拼凑方案更佳；
- ......
- f(15)：选择一张面值为 7 的纸币，那么 f(15) 的值可以用 1+f(8) 表示。1+f(8) = 3，比 f(15) 的当前值 15 小，表明 1+f(8) 的拼凑方案更佳。
更新表 2 中 f(7)~f(15) 对应的值，如表 3 所示：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 面值为 7 的纸币 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 2 | 3 |
3) 考虑选择面值为 10 的纸币，f(1)~f(15) 的计算过程是：
- f(1)~f(9)：无法选择面值为 10 个纸币；
- f(10)： 选择一张面值为 10 的纸币，那么 f(10) 的值可以用 1+f(0) 表示，1 指的是一张面值为 10 的纸币，f(0) 指的是拼凑金额 0 所需纸币的最少数量。1+f(0) = 1，比 f(10) 的当前值 4 小，表明 1+f(0) 的拼凑方案更佳；
- f(11)： 选择一张面值为 10 的纸币，那么 f(11) 的值可以用 1+f(1) 表示。1+f(1) = 2，比 f(11) 的当前值 5 小，表明 1+f(1) 的拼凑方案更佳；
- f(12)： 选择一张面值为 10 的纸币，那么 f(12) 的值可以用 1+f(2) 表示。1+f(2) = 3，比 f(12) 的当前值 6 小，表明 1+f(2) 的拼凑方案更佳；
- f(13)：选择一张面值为 10 的纸币，那么 f(13) 的值可以用 1+f(3) 表示。1+f(3) = 4，比 f(13) 的当前值 7 小，表明 1+f(3) 的拼凑方案更佳；
- f(14)：选择一张面值为 10 的纸币，那么 f(14) 的值可以用 1+f(4) 表示。1+f(4) = 5，比 f(14) 的当前值 2 大，表明先前的拼凑方案更佳；
- f(15)：选择一张面值为 10 的纸币，那么 f(15) 的值可以用 1+f(5) 表示。1+f(5) = 6，比 f(15) 的当前值 3 大，表明先前的拼凑方案更佳。
对于 f(14) 和 f(15) 来说，选择面值为 10 的纸币并没有先前的拼凑方案好，所以只更新表 3 中 f(10)~f(13) 对应的值，如表 4 所示：
| 选择的纸币 | f(n) 的所有情况 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | |
| 选择面值为 10 的纸币 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 3 |
最终，f(15) 对应的值是 3，表明拼凑出总面值 15 最少需要 3 张纸币。
零钱兑换问题的具体实现
下面是解决零钱兑换问题的伪代码，如果你理解了前面动态规划解决零钱兑换问题的思路，相信能很轻松地理解每行代码的含义。
// coins 存储纸币的不同面值，amount 表示要拼凑的总面值
minCoins(coins, amount):
n <- length(coins)
// 设置初始条件
dp[0] <- 0
// 创建一个数组来存储计算过的结果，初始化为无穷大
dp[1...amount] <- [INT_MAX, INT_MAX, ..., INT_MAX]
// 动态规划计算每个面值的最少纸币数量
for i <- 0 to n: // 遍历每个面值
for j <- coins[i] to amount: // 遍历 f(coins[i])~f(amount) 这些拼凑方案
if dp[j - coins[i]] != INT_MAX:
dp[j] = min(dp[j], dp[j - coins[i]] + 1)
// 返回凑齐面值 amount 所需的最少纸币数量
return dp[amount]
下面是动态规划解决零钱兑换问题的 C 语言程序：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 计算凑齐面值 n 所需的最少纸币数量
int minCoins(int coins[], int numCoins, int amount){
// 创建一个数组来存储计算过的结果，初始化为无穷大
int* dp = (int*)malloc((amount + 1) * sizeof(int));
// 设置初始条件
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
dp[i] = INT_MAX;
}
// 动态规划计算每个面值的最少纸币数量
for (int i = 0; i < numCoins; ++i) {
for (int j = coins[i]; j <= amount; ++j) {
if (dp[j - coins[i]] != INT_MAX) {
dp[j] = dp[j] < dp[j - coins[i]] + 1 ? dp[j] : dp[j - coins[i]] + 1;
}
}
}
// 返回凑齐面值 n 所需的最少纸币数量
return dp[amount];
}
int main() {
// 定义面值数组和数组长度
int coins[] = { 1, 7, 10 };
int numCoins = sizeof(coins) / sizeof(coins[0]);
int amount = 15;
int result = minCoins(coins, numCoins, amount);
if (result != INT_MAX) {
printf("凑齐面值 %d 最少需要 %d 张纸币\n", amount, result);
}
else {
printf("无法凑齐面值 %d\n", amount);
}
return 0;
}
下面是动态规划解决零钱兑换问题的 Java 程序：
public class MinCoins {
// 计算凑齐面值 n 所需的最少纸币数量
static int minCoins(int[] coins, int amount) {
// 创建一个数组来存储计算过的结果，初始化为无穷大
int[] dp = new int[amount + 1];
// 设置初始条件
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
dp[i] = Integer.MAX_VALUE;
}
// 动态规划计算每个面值的最少纸币数量
for (int coin : coins) {
for (int j = coin; j <= amount; ++j) {
if (dp[j - coin] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
}
// 返回凑齐面值 n 所需的最少纸币数量
return dp[amount];
}
public static void main(String[] args) {
// 定义面值数组
int[] coins = {1, 7, 10};
int amount = 15;
int result = minCoins(coins, amount);
if (result != Integer.MAX_VALUE) {
System.out.printf("凑齐面值 %d 最少需要 %d 张纸币\n", amount, result);
} else {
System.out.printf("无法凑齐面值 %d\n", amount);
}
}
}
下面是动态规划解决零钱兑换问题的 Python 程序：
def minCoins(coins, amount):
# 创建一个数组来存储计算过的结果，初始化为无穷大
dp = [float('inf')] * (amount + 1)
# 设置初始条件
dp[0] = 0
# 动态规划计算每个面值的最少纸币数量
for coin in coins:
for j in range(coin, amount + 1):
if dp[j - coin] != float('inf'):
dp[j] = min(dp[j], dp[j - coin] + 1)
# 返回凑齐面值 n 所需的最少纸币数量
return dp[amount]
if __name__ == "__main__":
# 定义面值数组
coins = [1, 7, 10]
amount = 15
result = minCoins(coins, amount)
if result != float('inf'):
print(f"凑齐面值 {amount} 最少需要 {result} 张纸币")
else:
print(f"无法凑齐面值 {amount}")
运行程序，输出结果为：
凑齐面值 15 最少需要 3 张纸币
ICP备案：
公安联网备案：