动态规划入门：硬币找零问题的C/C++实现与优化

1. 项目概述硬币找零问题的核心价值硬币找零Coin Change问题是算法领域一个经典得不能再经典的动态规划入门案例。我第一次接触它还是在大学的数据结构课上当时觉得这不就是个简单的数学问题吗但真正在面试和实际项目中遇到它的变种时才发现其背后蕴含的算法设计思想是理解“最优子结构”和“重叠子问题”这两大动态规划核心要素的绝佳桥梁。简单来说这个问题是给定一组不同面额的硬币比如1元、5元、10元和一个总金额计算凑成这个总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额则返回-1。这听起来像是个数学游戏但其应用场景远超你的想象。从自动售货机的找零逻辑到金融支付系统中的零钱兑换优化再到游戏里资源合成的最优路径计算本质上都是同一个模型。对于C/C开发者而言亲手实现一遍硬币找零算法不仅仅是刷一道LeetCode题那么简单。它能让你深刻理解如何将一个大问题分解成小问题如何用数组在C里可能是vector来存储中间状态以避免重复计算以及如何从递归的暴力搜索思维平滑过渡到迭代的动态规划思维。这个过程对于提升你解决复杂工程问题的“内力”至关重要。2. 算法核心思路与方案选型面对硬币找零问题我们通常有三种思路暴力递归、带备忘录的递归记忆化搜索、以及动态规划。每种方案的选择背后都是对时间复杂度和空间复杂度的权衡。2.1 暴力递归法最直观的误区最直接的想法是递归对于总金额amount尝试每一种面额的硬币coin然后递归求解子问题amount - coin。我们取所有可能解中的最小值。用C伪代码表示核心逻辑int coinChange(vectorint coins, int amount) { if (amount 0) return 0; if (amount 0) return -1; int res INT_MAX; for (int coin : coins) { int subProblem coinChange(coins, amount - coin); if (subProblem -1) continue; res min(res, subProblem 1); } return res INT_MAX ? -1 : res; }这个解法在思路上无比清晰但它有一个致命缺陷指数级的时间复杂度。假设硬币面额为[1,2,5]金额为100递归树会爆炸性增长因为amount-1、amount-2等子问题被重复计算了无数次。这是展示“重叠子问题”最生动的例子。所以暴力递归法在实际中几乎不可用但它是我们理解问题本质的起点。2.2 记忆化搜索自顶向下递归的优化既然子问题被重复计算一个自然的优化是用一个数组或哈希表把已经计算过的子问题的结果存起来。这就是带备忘录的递归也叫记忆化搜索。int dp(vectorint coins, int amount, vectorint memo) { if (amount 0) return -1; if (amount 0) return 0; if (memo[amount] ! -2) return memo[amount]; // -2表示未计算 int res INT_MAX; for (int coin : coins) { int subProblem dp(coins, amount - coin, memo); if (subProblem -1) continue; res min(res, subProblem 1); } memo[amount] (res INT_MAX) ? -1 : res; return memo[amount]; }初始化memo数组长度为amount1每个元素为-2一个不会与-1和0冲突的标记值。这个方法的时间复杂度降到了O(amount * n)其中n是硬币种类数。空间复杂度为O(amount)。记忆化搜索是连接递归思维和动态规划思维的桥梁它保留了递归的直观性又通过缓存避免了重复计算在面试中解释起来非常清晰。2.3 动态规划自底向上最终的工业级方案动态规划DP表格法是解决这个问题的标准答案。我们彻底抛弃递归从一个基础情况金额为0需要0个硬币开始一步步推导出目标金额的解。定义状态dp[i]表示凑成总金额i所需的最少硬币个数。状态转移方程对于每个金额i遍历每个硬币coin如果coin i那么dp[i]可以是dp[i - coin] 1。我们取所有可能中的最小值。dp[i] min(dp[i], dp[i - coin] 1) 对于所有coin i。初始化dp[0] 0。为了方便取最小值其他dp[i]初始化为一个很大的数比如amount 1因为最多用amount个1元硬币凑成。遍历顺序外层循环遍历金额i从1到amount内层循环遍历硬币数组。这是完全背包问题的遍历方式因为每种硬币可以使用无限次。注意为什么初始化为amount1因为最坏情况是用amount个1元硬币所以amount1是一个有效的“无穷大”标记。最后如果dp[amount]仍然是amount1说明无法凑出返回-1。方案选型总结对于硬币找零问题动态规划表格法是首选。它代码简洁效率稳定O(amount * n)没有递归栈溢出的风险是工程实践中的标准解法。记忆化搜索在理解上更有优势而暴力递归只存在于教科书里用于警示我们重叠子问题的代价。3. 核心源码实现与逐行解析下面我将给出C和C语言两个版本完整、健壮的实现并附上详细注释和边界处理。3.1 C标准实现使用vector#include vector #include algorithm #include climits class Solution { public: int coinChange(std::vectorint coins, int amount) { // 创建一个大小为 amount1 的DP数组并初始化为一个不可能的大值(amount1) // 使用 amount1 是因为最坏情况是用 amount 个1元硬币所以 amount1 相当于“无穷大” std::vectorint dp(amount 1, amount 1); // 基础情况凑出金额0需要0个硬币 dp[0] 0; // 外层循环遍历所有金额状态从1到amount // 这是自底向上构建解的过程 for (int i 1; i amount; i) { // 内层循环尝试使用每一种硬币 for (int coin : coins) { // 只有当当前硬币面值不大于目标金额时才可能使用它 if (coin i) { // 状态转移方程核心 // dp[i] 可能由 dp[i-coin] 加上当前这枚硬币转移而来 // 取所有可能情况中的最小值 dp[i] std::min(dp[i], dp[i - coin] 1); } } } // 最终dp[amount] 如果还是初始化的“无穷大”说明无法凑出 // 否则它就是最少硬币数 return dp[amount] amount ? -1 : dp[amount]; } };关键点解析dp数组初始化vectorint dp(amount 1, amount 1);这里创建了amount1个元素是因为金额从0到amount。初始化为amount1是一个技巧它保证了在后续min比较中任何有效的解都会小于这个值。dp[0] 0这是动态规划的“锚点”没有它整个递推就无法开始。凑0元当然需要0个硬币。双重循环顺序外层遍历金额i内层遍历硬币。这个顺序是正确的因为它确保了在计算dp[i]时所有更小金额dp[i-coin]都已经被计算过了因为i是从小到大遍历的。这体现了动态规划的“无后效性”。返回值判断return dp[amount] amount ? -1 : dp[amount];如果最终结果大于amount说明它从未被有效更新过即无法凑出。3.2 C语言实现手动管理数组对于嵌入式或对STL有限制的环境C语言版本同样重要。它涉及手动内存管理需要更谨慎。#include stdio.h #include stdlib.h #include limits.h int coinChange(int* coins, int coinsSize, int amount) { // 防御性编程处理异常输入 if (coins NULL || coinsSize 0) { return -1; } if (amount 0) { return -1; } if (amount 0) { return 0; } // 动态分配DP数组大小为 amount1 int* dp (int*)malloc((amount 1) * sizeof(int)); if (dp NULL) { return -1; // 内存分配失败 } // 初始化DP数组 for (int i 0; i amount; i) { dp[i] amount 1; // 初始化为“无穷大” } dp[0] 0; // 基础情况 // 动态规划核心过程 for (int i 1; i amount; i) { for (int j 0; j coinsSize; j) { int coin coins[j]; if (coin i) { // 状态转移注意防止整数溢出 if (dp[i - coin] ! amount 1) { int candidate dp[i - coin] 1; if (candidate dp[i]) { dp[i] candidate; } } } } } // 获取结果并释放内存 int result (dp[amount] amount) ? -1 : dp[amount]; free(dp); return result; }C版本特别注意内存管理必须使用malloc分配dp数组并在函数返回前用free释放否则会造成内存泄漏。这是C语言编程的基本功也是容易出错的地方。输入校验增加了对coins指针为空、数组大小为0、金额为负等情况的检查代码更健壮。溢出检查在状态转移时显式判断了dp[i - coin]是否为初始值然后再进行加1操作。虽然在这个问题里amount1作为最大值不太可能溢出但这是一个良好的编程习惯在处理更大数据范围时能避免潜在的未定义行为。3.3 算法复杂度与空间优化分析时间复杂度O(n * amount)。其中n是硬币种类数amount是目标金额。因为有两层嵌套循环。空间复杂度O(amount)。我们只需要一个长度为amount1的一维数组。关于空间优化有同学可能会问这是一个“完全背包”问题能否像01背包那样优化到一维数组并且内层循环正序遍历答案是我们现在用的已经是最优的空间复杂度了。因为硬币无限使用完全背包内层遍历硬币时dp[i]依赖的是本层更新过的dp[i-coin]因为coin可能很小i-coin在本轮i的循环中可能已经更新过了这恰好需要通过正序遍历金额来实现。而我们代码中外层循环i正是正序遍历所以当前的一维dp数组解法已经是空间最优解。如果内层循环倒序遍历就变成了每种硬币最多用一次的“01背包”问题了那是不符合题意的。4. 测试用例设计与边界陷阱写完代码不算完用全面的测试用例验证其正确性和鲁棒性是工程师的必备素养。下面是我常用的测试集// 假设有一个测试函数 void test() { Solution s; std::vectorint coins; // 1. 常规用例 coins {1, 2, 5}; std::cout s.coinChange(coins, 11) std::endl; // 期望输出: 3 (551) // 2. 无法凑出的情况 coins {2}; std::cout s.coinChange(coins, 3) std::endl; // 期望输出: -1 // 3. 金额为0 coins {1}; std::cout s.coinChange(coins, 0) std::endl; // 期望输出: 0 // 4. 大金额与小硬币 coins {1, 2, 5}; std::cout s.coinChange(coins, 100) std::endl; // 期望输出: 20 (20个5元) // 5. 包含面额大于总金额的硬币 coins {7, 10}; std::cout s.coinChange(coins, 8) std::endl; // 期望输出: -1 (78? 不78但8-71无法凑) // 注意这里容易出错算法会尝试用7然后发现dp[1]无法凑出。 // 6. 空硬币数组 coins {}; std::cout s.coinChange(coins, 10) std::endl; // 期望输出: -1 // 7. 负金额如果函数没做检查 // coins {1}; // std::cout s.coinChange(coins, -1) std::endl; // 应进行防御性处理 }实操心得与避坑指南初始化值的陷阱dp数组的初始值不能是INT_MAX。因为状态转移中有dp[i - coin] 1如果dp[i-coin]是INT_MAX加1会导致整数溢出在C/C中是未定义行为通常变成负数。所以用amount1是更安全的选择。遍历顺序的理解一定要理解为什么是“先遍历金额再遍历硬币”。你可以想象成对于当前要凑的金额i我挨个检查每一种硬币coin看用了它之后剩下的子问题i-coin有没有解。这个顺序符合我们对问题的直观思考。C语言的内存泄漏在C版本中每个malloc都必须对应一个free。特别是在函数有多个返回出口比如错误处理时很容易忘记释放内存。一个技巧是在函数开头就规划好唯一的出口并在那里统一释放资源。浮点数面额经典硬币找零问题假设面额是整数。如果面额是浮点数比如0.1, 0.5元通常的做法是将所有面额和总金额乘以10的幂次如10、100转换为整数再套用整数算法。但要注意转换过程中的精度损失最好使用定点数或高精度库处理。5. 算法变种与扩展思考掌握了基础版本我们可以看看一些常见的变种问题这能极大加深对动态规划的理解。5.1 变种一计算凑出总金额的“组合数”这是LeetCode上的另一道经典题518. 零钱兑换 II。问题变为计算可以凑成总金额的硬币组合数假设每种面额的硬币有无限个。注意顺序不同的序列被视作相同的组合。思路解析 此时dp[i]的定义需要改变表示凑成总金额i的硬币组合数。 状态转移方程变为dp[i] dp[i - coin]对于所有coin i。关键区别在于遍历顺序为了求组合数而非排列数我们必须先遍历硬币再遍历金额。这样可以保证在考虑一种硬币时不会重复计算由不同顺序构成的相同组合。int change(int amount, vectorint coins) { vectorint dp(amount 1, 0); dp[0] 1; // 凑成0元有一种组合什么都不选 for (int coin : coins) { // 先硬币 for (int i coin; i amount; i) { // 后金额且从coin开始 dp[i] dp[i - coin]; } } return dp[amount]; }如果调换两个循环的顺序变成先金额后硬币那么(1,2)和(2,1)会被算作两种不同的方式得到的就是排列数了。这个细微的差别是面试常考点。5.2 变种二硬币数量有限多重背包如果每种硬币coins[i]最多只能使用counts[i]次这就变成了“多重背包”问题。解法不再是一维DP而是需要增加一个维度来记录使用次数或者使用“二进制优化”或“单调队列优化”将其转化为01背包问题。这超出了基础硬币找零的范围但知道这个方向能让你明白动态规划问题的广阔天地。5.3 扩展如何输出具体的硬币组合有时我们不仅需要最少硬币数还需要知道是哪几个硬币。这需要在动态规划过程中记录“选择”。实现方法额外使用一个choice数组choice[i]记录在凑出金额i的最优解中最后使用的那枚硬币的面额。在状态转移更新dp[i]时同时更新choice[i] coin。最后我们从amount开始不断回溯coin choice[amount]然后amount - coin直到amount为0收集到的coin序列就是一组最优解可能不唯一此方法输出其中一种。vectorint coinChangeWithPath(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); vectorint choice(amount 1, -1); // 记录选择 dp[0] 0; for (int i 1; i amount; i) { for (int coin : coins) { if (coin i dp[i - coin] 1 dp[i]) { dp[i] dp[i - coin] 1; choice[i] coin; // 记录这步选择了哪个硬币 } } } if (dp[amount] amount) return {}; // 无法凑出 // 回溯构造路径 vectorint path; int remaining amount; while (remaining 0) { int coin choice[remaining]; path.push_back(coin); remaining - coin; } return path; }硬币找零问题就像算法世界里的“Hello World”它简单到足以入门又深刻到足以窥见动态规划的全貌。从暴力递归到记忆化搜索再到标准的动态规划表格法每一步优化都对应着对问题本质更深一层的理解。我建议你在理解上述代码后合上电脑在白纸上从amount11, coins[1,2,5]开始手动模拟一遍dp数组的填充过程。当你清晰地看到dp[11]如何从dp[10]、dp[9]、dp[6]推导而来时那种“顿悟”的感觉比死记硬背十道题都有用。最后别忘了用各种边界用例去测试你的代码这是将知识转化为可靠工程能力的最后一步。