企业官网建设流程全解析

讲个挺常见的场景：我帮几个朋友对面试题的时候，发现不少人一看到“兑换零钱”四个字，第一反应就是“简单，用贪心，先把最大面额塞满”。结果题目里的面额一特殊，当场就翻车了。这道题其实是个非常标准的动态规划模型，搞懂它，相当于是把“完全背包”“状态定义”“一维滚动数组优化”这几个高频考点一口气串起来了。今天我就以某刷题平台上编号BM70的这道《兑换零钱（一）》为例，从最原始的暴力想法开始，一步步推到动态规划解法，把代码、细节、坑全部摊开讲。

这篇文章适合两类人：一类是正在刷题准备面试的，想彻底搞懂“最少硬币数量”这类问题的套路；另一类是看题解经常能看懂、但自己上手就不知道怎么定义状态的同学。我会尽量把每一步“为什么这样做”都解释清楚，而不是只丢一段标准答案。

1. 先搞清楚题目到底在问什么

1.1 输入输出与边界条件

题目描述很简短：给一个数组arr，数组里每个值都是正整数，而且互不重复，每个值代表一种纸币面额；再给一个目标金额aim。每种面额的纸币都可以使用任意张，问凑出aim这个金额最少需要多少张纸币，如果无论如何都凑不出来，就返回-1。

举个例子最直观：

• 输入 arr = [5, 2, 3]，aim = 20
• 输出应该是 4

20元怎么凑？20 = 5 + 5 + 5 + 5，4张；20 = 5 + 5 + 5 + 2 + 3 是5张；20 = 2 + 3 + 5 + 5 + 5 也是5张。所以最少是4张。

这里有几个边界条件要格外注意：

• aim = 0：不需要任何货币，返回0。
• arr为空：没有任何面额能用，返回-1。
• aim小于0：输入不合法，正常应该返回-1。

还有一个容易被忽略的点：arr里的面额“互不重复”是题目给定的性质，实际写代码可以做假设，不用专门去重，但要用到它来简化问题分析。另外每个面额都是正整数，这一点很重要，因为如果是负数或零，整个状态递推就不成立了。

很多人看完题意就开始写代码，但没想清楚一件事：这道题问的是“最少张数”，不是“是否凑得出来”，也不是“有多少种凑法”。这三个问法虽然都是零钱兑换家族的，但状态定义和转移方程完全不一样。最少张数这个问法本身，就决定了它是一个最优化问题，而不是计数问题，所以后面定义dp时一定要围绕“最小化张数”来做。

1.2 为什么一上来就用贪心会翻车

贪心思路很自然：每次都拿面额最大、但不超过剩余金额的纸币，一直凑到目标。比如你手里有1元、5元、10元，要去凑14元，贪心先拿10元，再拿4张1元，一共5张；这确实是最优的。

但问题是，贪心的正确性依赖货币体系本身的设计。在真实世界里，人民币1、5、10、20、50、100这种结构里，贪心是能保证最优的，因为面额之间有倍数关系。算法题里的arr是任意给的，可不会这么善良。

经典反例就是 arr = [1, 5, 11]，aim = 15。

贪心会这么做：先取11，剩余4元，只能用4张1元，总共5张。 实际上最优解是：3张5元，5 + 5 + 5 = 15，只要3张。

差距立刻体现出来了。为什么贪心会错？因为你选了一张大面额，往往就要用很多小面额来“找零”，张数被拉高了；而选一个适中的面额，反而能刚好凑整。所以问题本质上需要搜索所有可能的组合，不能靠局部最优蒙混过关。

而暴力枚举所有组合，复杂度就是指数级的。硬币数量一多、目标金额一大，程序就爆炸了。这时候就需要动态规划登场，把重复计算的子问题缓存下来，用空间换时间。

2. 动态规划的核心推导：从状态定义到转移方程

2.1 状态定义是怎么想出来的

做动态规划，最关键的一步就是定义dp数组的含义。定义对了，转移方程自然就出来了；定义错了，后面全白搭。

这道题我建议从递归的角度倒推：假设我已经能凑出金额 i - coin，那么我再拿一张面额为coin的纸币，就能凑出金额 i。于是凑出金额 i 的最少张数，就等于“凑出 i - coin 的最少张数 + 1”。但coin有很多种，所以要遍历所有面额，取最小值。

把这种思考固化下来，就得到状态定义：

dp[i] 表示凑出金额 i 所需的最少纸币张数。

目标就是 dp[aim]。

你会发现这个定义天然只依赖金额这一个维度，没有把“用了哪几种面额”加进去。这是因为题目不限制每种面额的使用次数，也不关心你具体用了哪些面额的组合，只关心最终张数。维数越少，状态空间越小，这也是动态规划优化的一个基本原则：能用一维表示，就不要轻易上二维。

这里可以用一个生活化的类比：你玩游戏攒金币，每关可以选不同的任务完成，任务的奖励金币数不同。问你最少做几个任务能攒到目标金币。这里的“任务金币数”就好比“硬币面额”，“做任务的数量”好比“硬币张数”，每个任务可以反复做。dp[i]就是攒到i金币的最少任务数。

2.2 状态转移方程是怎么推出来的

动态规划的转移方程不是凭空想出来的，它是“最后一步”思维的产物。

凑出金额 i，拿最后一张纸币之前，手里的金额一定是 i - coin，其中coin是这张纸币的面额。在拿到这张纸币之前，凑出 i - coin 已经用了 dp[i - coin] 张纸币。那么现在总张数就是 dp[i - coin] + 1。

因为coin可以从arr里任意选，所以：

dp[i] = min(dp[i - coin] + 1)，遍历所有满足 coin ≤ i 的coin。

用代码写出来，往往会写成更通用的形式：

dp[i] = min(dp[i], dp[i - coin] + 1)

这种写法的意思是，一开始dp[i]是一个很大的数（代表还没算出来），每尝试一种硬币面额，就看看从金额 i - coin 转移过来是不是更少张数，是就更新。

这里有个细节值得说清楚：如果 dp[i - coin] 本身是“不可达”的，那 dp[i - coin] + 1 也是一个很大的值，不会成为最小值，所以它可以被自然淘汰。也就是说，转移方程里不用显式判断“ i - coin 是否可达”，初始化时用哨兵值就能自动处理。

2.3 初始化的哨兵值为什么是 aim + 1

初始化是这道题的另一个要点，也是新手最容易出问题的地方。

dp[0] = 0，这是空集，凑出0元当然一张都不用。

那 dp[1] 到 dp[aim] 初始化成什么？很多人会随手填0或者填一个很大的数比如10000。填0会出大问题：一旦和后面 dp[i - coin] + 1 做 min 比较，0永远是最小的，整个dp数组就全是0了，递推直接失效。

所以必须填一个“不可能被超越的大数”，代表“这个金额目前凑不出来”。这个数的选法有讲究，我个人的习惯是填 aim + 1。

为什么是 aim + 1？原因很简单：任何可行方案的张数，都不可能超过aim。因为每一张纸币的面额最小是1（arr都是正整数），即便你用全1元纸币，凑aim最多也就用aim张。如果存在更小面额，张数会更少。所以只要金额是可达的，dp[i] 一定小于等于 aim。用 aim + 1 这个值来代表“不可达”，就绝对不会和真实答案混淆。

当然也可以用 float('inf')，但用整数哨兵有两个好处：一是避免了浮点数在某些语言里的比较陷阱，二是在最后判断 dp[aim] == aim + 1 时非常直观。我平时讲题喜欢用整型哨兵，纯粹是图省心。

填表顺序也得注意：dp[i] 依赖的是 i - coin，也就是比 i 小的金额，所以从 dp[1] 到 dp[aim] 从小到大依次计算就对了。

3. 一维优化的完整实现：代码、循环顺序与细节

3.1 为什么能压成一维数组

有的教材在讲动态规划时会先给出二维版本，再用滚动数组优化。这道题本身其实可以不用二维，但理解二维到一维的压缩过程，对面试表达很有帮助。

如果非要用二维dp来表示，可以定义为：

dp[i][j] 表示用前 i 种面额的纸币凑出金额 j 的最少张数。

转移有两种情况：

• 不使用第 i 种面额：dp[i-1][j]
• 使用第 i 种面额：dp[i][j - arr[i]] + 1

注意第二个式子用的是 dp[i][j - arr[i]] 而不是 dp[i-1][j - arr[i]]，原因就在于“第 i 种面额可以用任意多张”。如果我用了第 i 种面额一张之后，还允许继续用第 i 种面额，就得看当前行的左边，而不是上一行。这是完全背包和01背包在二维写法上的核心区别。

观察发现，dp[i] 这一行只依赖上一行和当前行左边的位置，所以可以用一维数组反复覆盖更新。从左往右填，左边的 dp[j - arr[i]] 已经是当前轮次更新过的值，它天然代表了“已经用过第 i 种面额”的情况，这样正好实现了无限次使用。

这也是为什么很多算法书强调：完全背包的一维循环要正序，而01背包的一维循环要倒序。倒序的本意是防止同一种物品被重复取用，正序则是有意允许它重复取用。这个地方如果只是死记“正序/倒序”而不知道原因，面试官多问一层很容易露馅。

3.2 两种常见写法的代码与测试

第一种写法更贴合状态转移方程本身，外层循环遍历金额，内层循环遍历硬币面额：

def min_money(arr, aim): if not arr or aim < 0: return -1 INF = aim + 1 dp = [INF] * (aim + 1) dp[0] = 0 for i in range(1, aim + 1): for coin in arr: if coin <= i and dp[i - coin] + 1 < dp[i]: dp[i] = dp[i - coin] + 1 return dp[aim] if dp[aim] != INF else -1

第二种写法更贴近纯背包套路，外层循环遍历硬币面额，内层正序遍历金额：

def min_money(arr, aim): if not arr or aim < 0: return -1 INF = aim + 1 dp = [INF] * (aim + 1) dp[0] = 0 for coin in arr: for i in range(coin, aim + 1): if dp[i - coin] + 1 < dp[i]: dp[i] = dp[i - coin] + 1 return dp[aim] if dp[aim] != INF else -1

两种写法的空间复杂度都是 O(aim)，时间复杂度都是 O(aim × n)，其中 n 是面额的种类数。唯一要注意的是，第二种写法里 i 直接从 coin 开始，因为当 i < coin 时，i - coin 变成负数，没有意义。

我们用题目里 arr = [5, 2, 3]，aim = 20 来手推一遍第二种写法，感受一下过程：

• 初始 dp = [0, 21, 21, 21, ..., 21]
• 处理面额5：dp[5]=1, dp[10]=2, dp[15]=3, dp[20]=4
• 处理面额2：dp[2]=1, dp[4]=2, dp[6]=3, dp[8]=4, dp[10]保持2, dp[12]=3, dp[14]=4, dp[16]=5, dp[18]=6, dp[20]保持4
• 处理面额3：dp[3]=1, dp[6]=min(3, 2)=2, dp[9]=3, dp[12]=min(3,3)=3, dp[20]保持4

最终 dp[20] 还是4，符合预期。如果你把中间状态打印出来，能看到dp数组逐渐被“填满”，这个过程非常直观，建议调试时试一次。

我在面试或实际刷题时更常用第一种写法，因为它跟“dp[i] 表示凑出金额i的最少张数”这句话是逐字对应的，讲给别人听的时候逻辑最顺。但如果你对背包模型特别熟，第二种写法会更“通用”，因为以后做多重背包、完全背包的变体，都能沿用类似框架。两种写法都对，关键是别搞混循环方向。

3.3 复杂度还能不能再优化

很多人在写完这道题后都会问一句：时间复杂度O(aim × n)，空间O(aim)，能不能再优化？

对于这个具体问题，空间上很难再压成一两个变量了，因为计算 dp[i] 时依赖的是 i - coin，不同coin的跨度不同，你不能像斐波那契那样只保留两个数。所以 O(aim) 的空间是这类“重量型”DP的正常开销。

时间复杂度上，如果aim特别大，例如到了10的9次方级别，常规DP数组直接开不出来，那时候就需要另辟蹊径，比如利用硬币面额之间的关系做同余分类，或者转成最短路模型来解。但这些属于进阶玩法，面试和日常刷题基本不会考这么深，能把O(aim × n)的写法讲明白已经非常够用了。

4. 踩坑实录：这些错误我调试了不止一次

4.1 无解时把哨兵值直接输出了

我见过不少朋友写完代码跑第一个case没问题，结果第二个case arr=[2], aim=3 就醒了：代码输出 4，而不是 -1。

原因很简单：初始化用了 INF = aim + 1，也就是4，dp[3]一直没能被更新，最后输出时忘了判断是否等于INF，直接 return dp[aim]，于是4被当成答案抛出去了。

这个错误的教训是：使用哨兵值，就必须在最后做一次“可达性检查”。不要偷懒省掉那行if，否则索引越界和错误答案早晚出现一个。

4.2 外层金额、内层硬币时漏掉了条件

第一种写法里，内层循环遍历coin时，必须要先判断 coin <= i。有的人图省事写成：

dp[i] = min(dp[i], dp[i - coin] + 1)

当 coin > i 时，dp[i - coin] 的索引就变成负数了。Python里写负数索引不会直接报错，而是去访问数组末尾的元素，这个bug非常阴险，结果完全错乱但程序不崩溃，排查半天才发现是负数索引搞的鬼。要么加 if 判断，要么让coin只遍历到当前amount为止，千万别在Python里踩这个“负索引陷阱”。

4.3 完全背包被写成了01背包

前面强调过，完全背包一维要用正序。但新手很容易把模板背混，写成：

for i in range(aim, coin - 1, -1): dp[i] = min(dp[i], dp[i - coin] + 1)

这种倒序写法在01背包里是对的，但在本题就是错的。arr=[1, 3, 4], aim=6 能很好地暴露问题：正确答案是6张1元，3+3两张，或者1+1+4三张，所以最优是2张。但如果用倒序，同一个面额不会被重复利用，dp结果会偏大甚至完全错误。

我自己排查这个问题时最有效的方法是打印中间dp数组。倒序写法时你会发现，处理面额3时，dp[6]永远看不到dp[3]在“本轮”刚被更新过的值；而正序写法就能看到。这种对比一旦亲眼看到，就再也不会混了。

4.4 二维DP的时候忘了“不用第i种面额”这条转移

如果你在纸上写的是二维dp，或者是面试时先用二维思路讲一遍，然后是后面压成一维，那有一条转移线特别容易丢：不想用第i种面额时，应该直接继承 dp[i-1][j]。

很多人一看到“完全背包”就只记得 min(dp[i][j - arr[i]] + 1, ...)，完全忘了 dp[i-1][j] 这个“不选”的分支。结果就是，所有金额都必须至少用一次当前面额才能达到，明显错误。

我推荐的二维完整写法是：

dp[i][j] = min(dp[i-1][j], dp[i][j - arr[i]] + 1)

把它写全，再观察它其实只依赖上一行和当前行左侧，然后压缩成一维，思路才顺。这也是为什么我建议面试时先讲二维、再讲优化，而不是上来就给一维代码。

5. 从这道题往远处看：同类型变体与面试进阶

5.1 变体一：求凑出aim的方案总数

把问题从“最少几张”改成“一共有多少种凑法”，就是经典的原问题变体。这个变体特别能考你对“内外层循环顺序”的理解。

求方案数时，dp[j] 表示凑出金额j的方案数，初始 dp[0] = 1，表示空集是一种方案。

两种写法得到的结果完全不同：

• 外层遍历硬币，内层正序遍历金额：得到的是组合数，不区分顺序。
• 外层遍历金额，内层遍历硬币：得到的是排列数，区分顺序。

举个例子，arr=[1, 2]，aim=3。组合数是2种：1+1+1、1+2；排列数是3种：1+1+1、1+2、2+1。差别很大。

原因也很本质：外层遍历硬币时，相当于把硬币按“种类”分组，每种硬币只作为一个“物品类别”来处理，同一个组合不会因为先后顺序不同被重复统计；而外层遍历金额时，每次都在选择“最后一张硬币”，那1+2和2+1就被当成两种路径，算成排列数了。写这道求方案数的题目时，这个区分是必考点，也建议顺手做一遍。

5.2 变体二：返回具体的找零方案

面试时有的面试官会追加一句：不只返回张数，把具体用了哪些面额也一起返回。

在本题基础上，只需要额外维护一个身份数组 choice[i]，记录达到 dp[i] 时最后一次使用的是哪枚硬币。更新dp的同时更新choice：

for coin in arr: for i in range(coin, aim + 1): if dp[i - coin] + 1 < dp[i]: dp[i] = dp[i - coin] + 1 choice[i] = coin

最后从 aim 开始回溯：

res = [] cur = aim while cur > 0: c = choice[cur] res.append(c) cur -= c res.reverse() return res

如果 dp[aim] 是 INF，说明无解，直接返回空列表。这个方法不仅直观，而且复杂度跟原题一致，不会额外增加太多的空间负担。我实际试过，choice数组的长度和dp一样，都是 aim + 1，空间还是O(aim)。

5.3 变体三：每种硬币变成了有限张

如果题目改成每种面额的硬币最多只能使用k张，就变成多重背包问题了。基本思路是把第i种硬币当成k个独立物品，转化成01背包来做；数量特别大时，还可以用二进制分组优化，把k件物品拆成若干份，使得任意0~k的取用数量都能被这些份组合出来，从而把复杂度降下来。

这个变体跟本题的难度不在一个层级，但如果在面试中主动提一句“如果是有限张，我会用多重背包的二进制分组转换”，会给面试官留下“这个人体系的完整度不错”的印象。至于实现，面试时讲思路为主，不用真的写一遍。

5.4 面试时怎么把这题聊出亮点

这道题在面试里出现频率非常高，但大多数候选人只会背一个答案。我的建议是，讲的时候按这条递进线来组织：

• 第一步，先说暴力递归思路：枚举最后一枚硬币的面额，递归求解子问题。
• 第二步，指出暴力递归有大量重叠子问题，比如凑15和凑10都要反复算f(5)之类。
• 第三步，说用记忆化搜索，加一个数组缓存已算过的金额。
• 第四步，说既然递归是自顶向下，改写成自底向上循环就是动态规划，dp[0]=0，从小到大填表。
• 第五步，再说空间优化：观察转移只依赖更小的金额，可以压成一维数组；因为硬币无限，内层循环用正序。

这套话术的优势在于，你没有直接“背模板”，而是展示了自己从暴力到最优的完整思维过程。面试官往往更看重这个推导过程，而不是代码本身。

最后再提一个小建议：算法题“看懂答案”和“自己写对”之间隔着大量细节。你可以在本地编辑器里把 arr=[5,2,3], aim=20 这个例子从 dp[0] 手动推到 dp[20]，再用两种循环顺序各跑一遍，观察 dp 数组是怎么一步步变化的。这个看似笨拙的动作，能让你对完全背包的正序循环产生肌肉记忆。我自己当年就是在这一步突然想通的，之后遇到零钱兑换的各类变体，基本不会再瞎。