零钱兑换问题（Coin Change）是一个经典的动态规划问题，目标是找出组成给定金额所需的最少硬币数量。
问题描述
给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
假设：
- 硬币数量无限
- 硬币面额都是正整数
- 总金额 amount 是非负整数
方法一：暴力递归（回溯法）
思路分析
通过递归尝试所有可能的硬币组合，找出使用硬币数量最少的方案。
时间复杂度
O(Sⁿ)，其中 S 是金额，n 是硬币种类数
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 方法一：暴力递归
class Solution1 {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount < 0) return -1;
if (amount == 0) return 0;
int minCoins = INT_MAX;
for (int coin : coins) {
// 尝试使用当前硬币
int res = coinChange(coins, amount - coin);
if (res >= 0) {
minCoins = min(minCoins, res + 1);
}
}
return minCoins == INT_MAX ? -1 : minCoins;
}
};
方法二：记忆化递归（自上而下）
思路分析
在暴力递归的基础上，使用记忆化技术存储已经计算过的子问题结果，避免重复计算。
时间复杂度
O(S * n)，其中 S 是金额，n 是硬币种类数
代码实现
// 方法二：记忆化递归
class Solution2 {
public:
int coinChange(vector<int>& coins, int amount) {
// memo[i] 表示组成金额 i 所需的最少硬币数
vector<int> memo(amount + 1, -2); // -2 表示未计算
return dfs(coins, amount, memo);
}
private:
int dfs(vector<int>& coins, int amount, vector<int>& memo) {
if (amount < 0) return -1;
if (amount == 0) return 0;
// 如果已经计算过，直接返回结果
if (memo[amount] != -2) return memo[amount];
int minCoins = INT_MAX;
for (int coin : coins) {
int res = dfs(coins, amount - coin, memo);
if (res >= 0) {
minCoins = min(minCoins, res + 1);
}
}
// 记录计算结果
memo[amount] = (minCoins == INT_MAX) ? -1 : minCoins;
return memo[amount];
}
};
方法三：动态规划（自下而上）
思路分析
使用动态规划数组 dp[i] 表示组成金额 i 所需的最少硬币数。通过递推公式逐步计算。
状态转移方程
dp[i] = min(dp[i], dp[i - coin] + 1)，对于所有 coin <= i
时间复杂度
O(S * n)，其中 S 是金额，n 是硬币种类数
代码实现
// 方法三：动态规划
class Solution3 {
public:
int coinChange(vector<int>& coins, int amount) {
// dp[i] 表示组成金额 i 所需的最少硬币数
vector<int> dp(amount + 1, amount + 1);
// 初始化：组成金额 0 需要 0 个硬币
dp[0] = 0;
// 计算每个金额的最小硬币数
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
// 如果 dp[amount] 仍然是初始值，说明无法组成该金额
return dp[amount] > amount ? -1 : dp[amount];
}
};
方法四：动态规划优化（使用一维数组）
思路分析
对方法三进行空间优化，但本质上与方法三相同。
代码实现
// 方法四：动态规划优化
class Solution4 {
public:
int coinChange(vector<int>& coins, int amount) {
// dp[i] 表示组成金额 i 所需的最少硬币数
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
// 优化：先对硬币排序，可以减少部分比较
sort(coins.begin(), coins.end());
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin > i) break; // 硬币面额大于当前金额，无需继续
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
方法五：广度优先搜索（BFS）
思路分析
将问题转化为图论问题：每个节点表示一个金额，从 0 开始，每次添加一枚硬币到达新的金额，使用 BFS 找到到达目标金额的最短路径。
时间复杂度
O(S * n)，最坏情况下需要探索所有金额
代码实现
// 方法五：广度优先搜索
class Solution5 {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
queue<int> q;
vector<bool> visited(amount + 1, false);
q.push(0);
visited[0] = true;
int level = 0;
while (!q.empty()) {
int size = q.size();
level++;
for (int i = 0; i < size; i++) {
int current = q.front();
q.pop();
for (int coin : coins) {
int next = current + coin;
if (next == amount) {
return level;
}
if (next < amount && !visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
}
return -1;
}
};
方法六：贪心算法 + DFS（需要排序）
思路分析
先使用大面额硬币，再使用小面额硬币，通过深度优先搜索寻找最优解。这种方法不一定能得到最优解，但可以快速找到近似解，适用于某些特定场景。
注意
这种方法不保证总是得到最优解，但在硬币面额设计合理时可以工作。
代码实现
// 方法六：贪心 + DFS（不一定总是最优，但效率高）
class Solution6 {
public:
int coinChange(vector<int>& coins, int amount) {
// 按面额从大到小排序
sort(coins.rbegin(), coins.rend());
int ans = INT_MAX;
dfs(coins, amount, 0, 0, ans);
return ans == INT_MAX ? -1 : ans;
}
private:
void dfs(vector<int>& coins, int amount, int index, int count, int& ans) {
if (amount == 0) {
ans = min(ans, count);
return;
}
if (index == coins.size()) return;
// 剪枝：如果当前硬币数量已经超过已知最优解，提前返回
if (count >= ans) return;
// 尝试使用尽可能多的当前面额硬币
for (int k = amount / coins[index]; k >= 0 && count + k < ans; k--) {
dfs(coins, amount - k * coins[index], index + 1, count + k, ans);
}
}
};
测试代码
// 测试函数
void testCoinChange() {
vector<int> coins1 = {1, 2, 5};
int amount1 = 11;
vector<int> coins2 = {2};
int amount2 = 3;
vector<int> coins3 = {1, 3, 4};
int amount3 = 6;
// 测试不同方法
Solution1 s1;
Solution2 s2;
Solution3 s3;
Solution4 s4;
Solution5 s5;
Solution6 s6;
cout << "测试用例1: coins = [1, 2, 5], amount = 11" << endl;
cout << "暴力递归: " << s1.coinChange(coins1, amount1) << endl;
cout << "记忆化递归: " << s2.coinChange(coins1, amount1) << endl;
cout << "动态规划: " << s3.coinChange(coins1, amount1) << endl;
cout << "动态规划优化: " << s4.coinChange(coins1, amount1) << endl;
cout << "广度优先搜索: " << s5.coinChange(coins1, amount1) << endl;
cout << "贪心+DFS: " << s6.coinChange(coins1, amount1) << endl;
cout << endl;
cout << "测试用例2: coins = [2], amount = 3" << endl;
cout << "暴力递归: " << s1.coinChange(coins2, amount2) << endl;
cout << "记忆化递归: " << s2.coinChange(coins2, amount2) << endl;
cout << "动态规划: " << s3.coinChange(coins2, amount2) << endl;
cout << "动态规划优化: " << s4.coinChange(coins2, amount2) << endl;
cout << "广度优先搜索: " << s5.coinChange(coins2, amount2) << endl;
cout << "贪心+DFS: " << s6.coinChange(coins2, amount2) << endl;
cout << endl;
cout << "测试用例3: coins = [1, 3, 4], amount = 6" << endl;
cout << "暴力递归: " << s1.coinChange(coins3, amount3) << endl;
cout << "记忆化递归: " << s2.coinChange(coins3, amount3) << endl;
cout << "动态规划: " << s3.coinChange(coins3, amount3) << endl;
cout << "动态规划优化: " << s4.coinChange(coins3, amount3) << endl;
cout << "广度优先搜索: " << s5.coinChange(coins3, amount3) << endl;
cout << "贪心+DFS: " << s6.coinChange(coins3, amount3) << endl;
}
int main() {
testCoinChange();
return 0;
}
总结与比较
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力递归 | O(Sⁿ) | O(S) | 实现简单 | 效率极低，重复计算多 |
| 记忆化递归 | O(S * n) | O(S) | 避免重复计算 | 递归深度可能较大 |
| 动态规划 | O(S * n) | O(S) | 稳定可靠 | 可能需要计算所有子问题 |
| 动态规划优化 | O(S * n) | O(S) | 代码简洁 | 同动态规划 |
| 广度优先搜索 | O(S * n) | O(S) | 直观，易理解 | 可能需要探索所有状态 |
| 贪心+DFS | 不确定 | O(S) | 在某些情况下快 | 不保证最优解 |
推荐使用动态规划（方法三或四），因为它： 1. 保证得到最优解 2. 时间复杂度相对较低 3. 实现简单且稳定
对于特别大的金额，可以考虑使用贪心+DFS方法进行优化，但要注意验证是否适用于具体的硬币面额组合。