企业官网建设流程全解析

如果你正在学动态规划，大概率在"零钱兑换"（Coin Change）这道题上卡过。很多人能背出代码，但一被追问细节就懵——+1是什么意思？Integer.MAX_VALUE为什么要初始化？最后那行return res == Integer.MAX_VALUE ? -1 : res在干什么？

这篇文章把这些问题一个一个拆透。不跳步，不装懂，每一步都用人话解释。

一、问题是什么

给定硬币面额数组coins和目标金额amount，求凑出该金额的最少硬币数量。如果无法凑出，返回-1。

示例：coins = [1, 2, 5]，amount = 11

答案：3（因为11 = 5 + 5 + 1，用了 3 枚硬币）

二、+1到底是什么意思

这是整道题最核心的问题。书上的状态转移方程是：

dp(n)=min⁡{dp(n−coin)+1∣coin∈coins}dp(n) = \min\{dp(n - coin) + 1 \mid coin \in coins\}dp(n)=min{dp(n−coin)+1∣coin∈coins}

翻译成人话：

• dp(n)：凑出金额n最少需要几枚硬币
• dp(n - coin)：假设我先拿了一枚面额为coin的硬币，剩下的金额是n - coin，凑出这部分需要dp(n - coin)枚
• +1：就是我刚才拿的那一枚硬币

所以dp(n - coin) + 1的意思是：

先选一枚 coin，再加上凑剩余金额需要的硬币数

以coins = [1, 2, 5]，求dp(6)为例：

• 选 coin = 5：剩下 1 元，dp(1) = 1（用一枚 1），加上当前的 5，总共1 + 1 = 2枚
• 选 coin = 2：剩下 4 元，dp(4) = 2（2+2），加上当前的 2，总共1 + 2 = 3枚
• 选 coin = 1：剩下 5 元，dp(5) = 1（用一枚 5），加上当前的 1，总共1 + 1 = 2枚

取最小值，dp(6) = 2。

+1就是"我刚选的这一枚硬币"。记住这句话就够了。

三、递归代码逐行拆解

下面是暴力递归版，对应书上最原始的思路：

publicclassCoinChangeRecursive{publicstaticvoidmain(String[]args){int[]coins={1,2,5};intamount=11;System.out.println(dp(coins,amount));// 输出: 3}privatestaticintdp(int[]coins,intn){// base case 1：金额刚好凑完，不需要硬币if(n==0)return0;// base case 2：金额变成负数，这条路走不通if(n<0)return-1;// 初始化为"无穷大"，因为我们要取最小值intres=Integer.MAX_VALUE;// 尝试每一种硬币for(intcoin:coins){// 选一枚 coin，递归算剩余金额intsub=dp(coins,n-coin);// 子问题无解，跳过这种 coinif(sub==-1)continue;// 取最小值：当前这枚(+1) + 子问题的解res=Math.min(res,1+sub);}// 关键：如果所有 coin 都走不通，返回 -1；否则返回算出来的值returnres==Integer.MAX_VALUE?-1:res;}}

四、Integer.MAX_VALUE和最后那行 return 到底在干什么

这是另一个高频卡点。拆成三个问题来回答：

1. 为什么要初始化成Integer.MAX_VALUE？

因为我们在用Math.min求最小值。如果初始化成 0，Math.min(0, 1+sub)永远返回 0，逻辑就错了。所以必须初始化成一个"比任何正常答案都大的数"，让第一次比较能正常生效。Integer.MAX_VALUE就是 Java 里的"正无穷"。

2. 什么时候res会一直是Integer.MAX_VALUE？

只有当所有硬币都试过，而且每一条路都无解时。比如coins = [2, 5]，求dp(3)：

• 选 2：剩 1，继续递归，最终金额变负，返回 -1
• 选 5：剩 -2，直接返回 -1

两条路都continue了，res从来没被更新过，仍然是Integer.MAX_VALUE。

3. 最后那行 return 在干什么？

returnres==Integer.MAX_VALUE?-1:res;

拆开写就是：

if(res==Integer.MAX_VALUE){return-1;// 所有路都不通，无解}else{returnres;// 有解，返回最少硬币数}

它就是一个安全检查：如果res还是无穷大，说明真的凑不出来，返回 -1；否则返回算出来的结果。

五、用dp(3)完整走一遍

coins = [1, 2, 5]，求dp(3)：

dp(3) ├── coin=1 → dp(2) │ ├── coin=1 → dp(1) → dp(0)=0 → dp(1)=1 → 这条路: 1+1=2 │ ├── coin=2 → dp(0)=0 → 这条路: 1+0=1 │ └── coin=5 → dp(-3)=-1 → 跳过 │ dp(2) = min(2, 1) = 1 │ 所以 coin=1 这条路: 1 + dp(2) = 1 + 1 = 2 │ ├── coin=2 → dp(1) = 1 │ 所以 coin=2 这条路: 1 + 1 = 2 │ └── coin=5 → dp(-2) = -1 → 跳过 最终: min(2, 2) = 2

所以dp(3) = 2（用 1+2 或 2+1）。

六、备忘录版：消除重复计算

暴力递归的问题在于同一个n会被反复计算。加一个备忘录就能把时间复杂度从指数级压到O(amount × coins.length)：

importjava.util.HashMap;importjava.util.Map;publicclassCoinChangeMemo{publicstaticvoidmain(String[]args){int[]coins={1,2,5};intamount=11;Map<Integer,Integer>memo=newHashMap<>();System.out.println(dp(coins,amount,memo));// 输出: 3}privatestaticintdp(int[]coins,intn,Map<Integer,Integer>memo){if(memo.containsKey(n))returnmemo.get(n);if(n==0)return0;if(n<0)return-1;intres=Integer.MAX_VALUE;for(intcoin:coins){intsub=dp(coins,n-coin,memo);if(sub==-1)continue;res=Math.min(res,1+sub);}memo.put(n,res==Integer.MAX_VALUE?-1:res);returnmemo.get(n);}}

七、DP 数组版：自底向上

递归 + 备忘录是"自顶向下"，还可以反过来——从 0 开始一步步算到 amount：

publicclassCoinChangeDP{publicstaticvoidmain(String[]args){int[]coins={1,2,5};intamount=11;System.out.println(coinChange(coins,amount));// 输出: 3}privatestaticintcoinChange(int[]coins,intamount){int[]dp=newint[amount+1];for(inti=1;i<=amount;i++)dp[i]=amount+1;// 初始化为"无穷大"dp[0]=0;for(inti=1;i<=amount;i++){for(intcoin:coins){if(i-coin>=0){dp[i]=Math.min(dp[i],dp[i-coin]+1);}}}returndp[amount]>amount?-1:dp[amount];}}

填表结果：

八、总结

动态规划不是魔法，它只是三步：

1. 定义状态：dp(n)表示凑出金额n的最少硬币数
2. 找到选择：对每个n，尝试所有硬币面额
3. 写出转移：dp(n) = min(dp(n - coin) + 1)，其中+1就是当前这枚硬币

而Integer.MAX_VALUE和最后的return res == Integer.MAX_VALUE ? -1 : res，只是工程上的"初始化无穷大 + 无解兜底"，保证代码在任何情况下都能正确返回。

理解这些，零钱兑换这道题就真正吃透了。