1. 从一道经典面试题说起为什么找零钱不简单如果你刷过LeetCode或者准备过技术面试那么“找零钱问题”Coin Change绝对是一个绕不开的经典。题目描述通常很简单给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。听起来是不是很像你小时候帮妈妈去小卖部买东西老板找零时的场景但就是这个看似生活化的问题却成了无数程序员面试路上的“拦路虎”。我第一次遇到这个问题时直觉反应就是“贪心”从最大面额的硬币开始拿直到拿不了再换小面额的这不就是现实生活中我们找零的思路吗比如我们有1元、5元、10元要凑18元肯定是先拿一个10元剩下8元拿一个5元最后三个1元。一共5个硬币。这个直觉在硬币面额是“标准”的、成倍数关系时比如我们的人民币体系确实有效。但问题恰恰就出在这里——题目给出的硬币面额是任意的。如果硬币是[1, 3, 4]要凑6元贪心算法会先拿4剩下2元只能用两个1元来凑总共用了3个硬币411。但最优解其实是两个3元硬币只需要2个。看贪心在这里就“贪”错了它只看到了眼前的“最大利益”却可能错过了全局的更优解。正是这个“贪心可能失效”的特性让找零钱问题从一个简单的模拟题升级为了一个必须深入理解算法思想的典型例题。它完美地串联起了“贪心算法”和“动态规划”这两个核心的算法设计范式逼迫我们去思考什么时候可以“贪”什么时候必须“规划”这背后其实是计算机科学中“最优子结构”和“贪心选择性质”这两个核心概念的较量。搞懂了这个问题你不仅会解一道题更能深刻理解一大类组合优化问题的解题思路。接下来我们就先从这个让我们“翻车”的贪心算法开始彻底拆解它的工作原理和致命缺陷。2. 贪心算法的直觉与陷阱为什么“最大面额优先”会失灵当我们面对找零钱问题时大脑的第一反应往往是贪心策略因为它符合我们在现实世界中的经验而且实现起来简单直观。让我们先把这个直觉算法实现出来看看它到底是怎么工作的以及它会在哪里栽跟头。2.1 贪心算法的实现逻辑贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的。对于找零钱问题这个“局部最优”就是当前可用的最大面额硬币。用伪代码来描述这个过程非常清晰将硬币数组coins按面额从大到小排序。初始化一个计数器count 0用于记录硬币总数。遍历排序后的硬币数组当剩余金额amount大于等于当前硬币面额coin时计算最多能使用几枚当前硬币num amount / coin(整数除法)。更新硬币总数count num。更新剩余金额amount - num * coin。遍历结束后检查剩余金额amount是否为0。如果为0返回count。如果不为0说明无法凑出返回-1。用我们之前的人民币例子coins [1, 5, 10],amount 18来走一遍流程排序后为[10, 5, 1]。面对1018 / 10 1拿1个10元count1,amount8。面对58 / 5 1拿1个5元count2,amount3。面对13 / 1 3拿3个1元count5,amount0。成功返回5。结果正确。代码写出来也非常简洁以Python为例def coinChange_greedy(coins, amount): # 从大到小排序 coins.sort(reverseTrue) count 0 for coin in coins: if amount coin: num amount // coin count num amount - num * coin if amount 0: break return count if amount 0 else -1看起来完美无缺效率极高时间复杂度O(n log n)主要是排序之后是O(n)那为什么我们说它有陷阱呢2.2 深入分析贪心失效的根源贪心算法要能获得全局最优解必须满足一个关键性质贪心选择性质。意思是通过局部最优选择每次拿最大硬币能最终构造出全局最优解。这个性质成立需要很强的条件。让我们用反例coins [1, 3, 4],amount 6来深入剖析贪心路径拿4 - 剩2 - 拿1 - 剩1 - 拿1。共3枚硬币 (4,1,1)。最优路径拿3 - 剩3 - 拿3。共2枚硬币 (3,3)。贪心算法在这里为什么错了因为它第一步选择了面额4的硬币。这一步选择看似让剩余金额从6降到了2减少了4是最“贪”的。但正是这一步把后续的可能性给“堵死”了。剩余金额2只能用1元硬币来凑导致总硬币数增多。如果我们不从“拿了什么”看而从“还剩什么”看就能发现动态规划思想的苗头。凑6元的最优解取决于你凑6-coin元需要的最少硬币数再加1。即dp[6] min(dp[6-1], dp[6-3], dp[6-4]) 1 min(dp[5], dp[3], dp[2]) 1。 如果我们知道dp[2]2(11),dp[3]1(3),dp[5]3(41)那么min(3, 1, 2)1 2对应选择面额3的硬币。贪心算法在第一步根本没有去比较dp[2],dp[3],dp[5]这些子问题的解它武断地认为减少的金额最多就是最好的这在不满足“贪心选择性质”的硬币体系下是不成立的。注意一个常见的误解是只要硬币面额是“可整除”的比如12510这种贪心就有效。更准确地说贪心有效的充分条件是硬币体系是“规范”的Canonical Coin System但这需要数学证明。对于任意的硬币组我们无法一眼判断。因此在面试或竞赛中除非题目明确说明硬币面额是标准体系如美元、人民币否则默认贪心策略是不可靠的必须考虑动态规划。2.3 贪心算法的适用场景与教训虽然贪心算法不能解决通用的找零钱问题但它并非一无是处。在满足特定条件的场景下它依然是最高效的解法现实货币系统如人民币1,2,5,10,20,50,100、美元1,5,10,25等这些是设计好的规范体系贪心有效。部分题目约束有些LeetCode变种题会明确说明“你可以认为每种硬币的数量是无限的并且硬币面额是成倍数关系的”这时就可以放心使用贪心。那么从贪心算法的“翻车”中我们能学到什么直觉需要验证编程中直觉很重要但必须用严格的逻辑和反例来验证。遇到最值问题先问自己局部最优一定能导致全局最优吗理解问题本质找零钱问题的本质是“无限背包的最小物品数”问题。这类求“最小值”且物品可无限取用的题目动态规划是更通用的武器。从错误中学习贪心解法的错误恰恰引出了对动态规划的需求。它告诉我们当当前选择会影响未来所有选择时我们需要一个更“聪明”的方法来记住并比较所有可能的选择路径。既然贪心靠不住我们就必须请出更强大的方法——动态规划来系统地解决这个问题。接下来我们将一步步构建出动态规划的解法你会发现它的思路其实非常自然。3. 动态规划的正解构建“最少硬币数”的记忆地图当贪心算法因为目光短浅而失败时动态规划Dynamic Programming, DP提供了一种“高瞻远瞩”的解决方案。它的核心思想不是一次性做出选择而是系统地解决所有更小的子问题并把答案记下来避免重复计算最终组合出原问题的解。对于找零钱问题DP的思路异常清晰和直接。3.1 定义状态与推导状态转移方程这是DP最核心也最关键的一步想清楚了问题就解决了一大半。定义状态我们定义dp[i]表示凑成总金额i所需的最少硬币个数。我们的目标是求dp[amount]。为什么这样定义因为问题问的就是“最少硬币个数”很自然地将答案设为我们状态数组的值。i代表了问题的规模目标金额从0到amount。寻找状态转移方程思考如何从已知的小金额答案推导出大金额的答案。这是DP的精华所在。考虑最后一步假设我们已经凑出了金额i并且最后一步使用了一枚面额为coin的硬币。那么在凑出这最后一枚硬币之前我们已经凑出了金额i - coin。因此凑出金额i的最少硬币数应该是“凑出金额i - coin的最少硬币数”加上这最后一枚硬币也就是加1。但是我们不知道最后一步用的是哪个coin所以我们需要遍历所有可能的、且小于等于i的硬币面额并选择一个使得dp[i - coin] 1最小的那个。由此我们得到著名的状态转移方程dp[i] min(dp[i - coin1], dp[i - coin2], ..., dp[i - coinK]) 1其中coin是所有满足coin i的硬币面额。边界条件Base Casedp[0] 0凑出总金额为0需要0个硬币。这是所有计算的起点。对于无法凑出的金额i我们将其dp[i]初始化为一个很大的数比如amount 1或float(inf)表示“无穷大”或“不可达”。这样在取最小值时这些不可达的状态就不会被选中。3.2 自底向上的迭代实现标准解法有了状态和方程我们可以用迭代填表的方式来实现这是最经典也最易懂的DP实现方式。我们从一个具体的例子coins [1, 3, 4],amount 6来演示这个过程。算法步骤初始化dp数组长度为amount 1因为我们要存从0到amount的所有状态。dp[0] 0其他位置初始化为amount 1一个比最大可能硬币数都大的数这里617。外层循环i从 1 遍历到amount代表我们正在计算凑出金额i的最优解。内层循环遍历coins数组中的每一枚硬币coin。如果coin i说明这枚硬币可以用来凑i则尝试更新dp[i]dp[i] min(dp[i], dp[i - coin] 1)。循环结束后检查dp[amount]。如果它仍然等于初始化的那个大数说明无法凑出返回-1否则返回dp[amount]。手动填表演示初始化dp [0, 7, 7, 7, 7, 7, 7]i1: 硬币1可用。dp[1] min(dp[1], dp[0]1) min(7, 01) 1。dp [0, 1, 7, 7, 7, 7, 7]i2: 硬币1可用。dp[2] min(dp[2], dp[1]1) min(7, 11) 2。dp [0, 1, 2, 7, 7, 7, 7]i3: 硬币1和3可用。用1:dp[3] min(dp[3], dp[2]1) min(7, 21) 3用3:dp[3] min(3, dp[0]1) min(3, 01) 1dp [0, 1, 2, 1, 7, 7, 7]i4: 硬币1, 3, 4可用。用1:dp[4] min(dp[4], dp[3]1) min(7, 11) 2用3:dp[4] min(2, dp[1]1) min(2, 11) 2用4:dp[4] min(2, dp[0]1) min(2, 01) 1dp [0, 1, 2, 1, 1, 7, 7]i5: 硬币1, 3, 4可用。用1:dp[5] min(dp[5], dp[4]1) min(7, 11) 2用3:dp[5] min(2, dp[2]1) min(2, 21) 2用4:dp[5] min(2, dp[1]1) min(2, 11) 2dp [0, 1, 2, 1, 1, 2, 7]i6: 硬币1, 3, 4可用。用1:dp[6] min(dp[6], dp[5]1) min(7, 21) 3用3:dp[6] min(3, dp[3]1) min(3, 11) 2用4:dp[6] min(2, dp[2]1) min(2, 21) 2dp [0, 1, 2, 1, 1, 2, 2]最终dp[6] 2与我们之前分析的最优解两枚3元硬币一致。代码实现Pythondef coinChange(coins, amount): # 初始化dp数组dp[i]表示凑成金额i所需的最少硬币数 # 初始化为一个不可能的大值这里用 amount1因为最多用amount个1元硬币 dp [amount 1] * (amount 1) dp[0] 0 # 金额为0时不需要任何硬币 # 遍历所有金额状态从1到amount for i in range(1, amount 1): # 遍历每一种硬币 for coin in coins: # 如果当前硬币面额小于等于目标金额i则可以考虑使用它 if coin i: # 状态转移dp[i] min(dp[i], dp[i-coin] 1) dp[i] min(dp[i], dp[i - coin] 1) # 如果dp[amount]没有被更新过说明无法凑出 return dp[amount] if dp[amount] ! amount 1 else -1复杂度分析时间复杂度O(S * n)其中S是目标金额amountn是硬币面额种类数。我们需要计算S个状态每个状态需要遍历n种面额来转移。空间复杂度O(S)用于存储dp数组。这个解法是LeetCode上最标准的答案它可靠地解决了所有情况。然而动态规划的魅力不止于此我们还可以从不同的角度来思考这个问题有时能获得一些优化或启发。4. 动态规划的另一种视角完全背包问题如果你对动态规划的分类有所了解可能会认出找零钱问题其实是完全背包问题的一个变种。理解这个视角能帮你把这个问题归类到更广阔的算法知识体系中并借鉴背包问题的优化技巧。4.1 将问题转化为背包模型在背包问题中我们通常有背包容量对应这里的总金额amount。物品对应这里的硬币。每种硬币是一个“物品”。物品重量通常对应物品的“代价”。在这里如果我们把“使用一枚硬币”看作放入背包那么每枚硬币的“重量”就是它的面额coin。物品价值这是我们希望最大化或最小化的目标。在标准的背包问题是最大化价值。在这里我们的目标是“最小化硬币数量”所以我们可以把每枚硬币的价值视为1因为每用一枚硬币总数就加1。那么总价值就是使用的硬币总数我们要做的就是在恰好装满背包总金额等于amount的前提下使得总价值硬币总数最小。物品数量每种硬币有无限个这就是“完全”背包的特点。所以找零钱问题可以精确地描述为一个容量为amount的背包有n种物品硬币每种物品的重量为coins[i]价值为1且每种物品有无限个。求恰好装满背包时最小的总价值是多少如果无法恰好装满返回 -1。4.2 基于背包框架的DP实现与对比在完全背包问题中求“最小价值”的状态转移方程和我们之前推导的完全一致。但背包问题的经典写法内层循环通常是遍历物品硬币外层循环遍历容量金额并且内层循环是顺序遍历这与0-1背包的倒序遍历不同因为物品无限。这种写法有时更符合一些人的思维习惯先决定用哪个硬币再考虑能凑哪些金额def coinChange_pack(coins, amount): dp [amount 1] * (amount 1) dp[0] 0 # 外层遍历物品硬币 for coin in coins: # 内层顺序遍历容量金额因为是完全背包 for i in range(coin, amount 1): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! amount 1 else -1这个版本和之前“先金额后硬币”的版本在时间复杂度上是一样的O(S*n)并且对于找零钱问题两者等价。但在一些变种问题中遍历顺序可能会影响结果比如求组合数还是排列数。对于基础的最小硬币数问题两种顺序都可以。个人经验我刚开始学的时候觉得“先金额后硬币”的写法更直观因为它直接对应着状态转移方程dp[i] min(... dp[i-coin] ...)是在求解一个具体金额i时去尝试所有可能的“最后一步”。而“先硬币后金额”的背包写法更像是在说“引入了这个硬币后对所有能更新的金额状态进行刷新”。在面试中解释第一种通常更容易让面试官理解你的思路。4.3 从背包问题中获得的优化启示虽然基础DP解法已经足够但了解背包问题的优化思路是有益的。例如在完全背包问题中有一种基于“单调队列”的优化可以将时间复杂度优化到 O(S * n) 的理论下界但实现复杂在面试中不常见。更实用的是一些剪枝和常数优化硬币排序与提前终止在开始DP前可以先对coins数组进行排序。在内层循环遍历硬币时一旦遇到coin i因为硬币是升序排列后面的硬币面额更大肯定也大于i所以可以提前break内层循环。这能减少一些不必要的比较。coins.sort() # 排序 for i in range(1, amount 1): for coin in coins: if coin i: # 因为已排序后面的coin都大于i直接跳出 break dp[i] min(dp[i], dp[i - coin] 1)无效状态过滤如果dp[i - coin]是一个不可达的状态即其值等于初始化的最大值那么dp[i - coin] 1也没有意义可以跳过。不过在现代CPU上一次min比较的成本很低显式判断可能并不会带来显著提升有时反而增加分支预测开销。理解背包模型最大的好处是知识迁移。当你遇到“零钱兑换 II”LeetCode 518求凑成总金额的硬币组合数时你会立刻意识到这是完全背包的“组合数”问题状态转移方程从min变成了dp[i] dp[i - coin]并且遍历顺序需要仔细考虑先物品后容量求的是组合数先容量后物品求的是排列数。这种举一反三的能力比死记硬背一道题的解法重要得多。5. 从理论到实战编码细节、测试与常见陷阱掌握了核心算法思想最终还是要落到代码上。在实际编写和调试找零钱问题的DP解法时有几个细节和陷阱需要特别注意这些往往是面试官考察的重点也是新手容易出错的地方。5.1 初始化与边界条件的处理艺术dp数组的初始化看似简单实则暗藏玄机。初始值的选择为什么是amount 1理论上用float(inf)表示正无穷更直观。但在Python中整数运算比浮点数稍快且避免类型转换。amount 1是一个安全的上界因为即使全部用1元硬币最多也只需要amount个。任何有效的解都不会超过这个值。如果最终dp[amount]等于这个值就说明无解。陷阱千万不要初始化为0。因为我们的状态转移是取min如果初始化为0那么所有状态的最小值都会是0结果完全错误。dp[0] 0的重要性这是动态规划的“基石”。它表示凑出金额0需要0个硬币。没有这个定义dp[coin] dp[0] 1这样的转移就无法进行。你可以把它理解为“空集合”是一种合法的解总金额为0时不取任何硬币。金额为0的情况这是一个极易遗漏的边界Case。如果输入的amount就是0根据题目定义凑成总金额所需的最少硬币个数应该返回0因为不需要任何硬币。你的代码必须能正确处理amount 0的情况。在我们的循环中range(1, amount1)在amount0时不会执行dp[0]已经被初始化为0所以最后返回dp[0]即0。但如果你在函数开头没有特殊处理并且后面判断返回值时写成了if dp[amount] amount: return -1当amount0时就会出错因为dp[0]0不大于0。安全的写法是if amount 0: return -1 # 如果题目允许amount为负但通常不会 if amount 0: return 0 # 显式处理0的情况逻辑更清晰 dp [amount 1] * (amount 1) dp[0] 0 # ... DP过程 ... return dp[amount] if dp[amount] amount else -15.2 测试用例设计与调试技巧不要只相信样例自己设计全面的测试用例是写出健壮代码的关键。测试用例描述coinsamount预期结果检查点基础功能[1,2,5]113 (551)验证标准DP贪心失效[1,3,4]62 (33)验证算法正确性非贪心无解情况[2]3-1验证无法凑出时的返回金额为0[1]00验证边界条件大面额硬币[2,5,10]3-1验证小金额无法用大硬币凑包含面额1[1]55验证只有一种硬币硬币包含0[0,1,2]31 (理论上)注意实际题目硬币面额应为正整数此用例用于防御性编程在调试时除了看最终结果打印出整个dp数组是非常有用的手段。它能让你清晰地看到每个子问题的解是如何一步步推导出来的很容易发现状态转移中的逻辑错误。例如对于coins[2], amount3正确的dp数组应该是[0, 3, 1, 3]假设初始化为3。如果你看到dp[1]变成了1那肯定是状态转移的条件if coin i写错了或者没有正确处理无解状态。5.3 易错点与性能考量循环变量与索引在内外层循环中小心混淆i当前金额和coin硬币面额。特别是在状态转移方程dp[i] min(dp[i], dp[i - coin] 1)中确保i - coin作为索引是有效的非负。我们的条件if coin i保证了这一点。空间优化标准的DP使用了 O(amount) 的空间。在某些极端情况下如amount非常大可能会考虑空间优化。由于完全背包问题的状态转移只依赖于上一行如果先物品后容量或当前行左边的状态如果先容量后物品理论上可以优化到 O(amount) 的一维数组我们的写法已经是一维的了。进一步优化空间意义不大。时间优化对于某些特定情况可以提前判断。例如如果硬币面额列表的最小值min(coins) 1那么金额1肯定无法凑出所有不是最小公倍数倍数的金额可能都无法凑出但这属于数学优化通用性不强。在面试中给出标准的 O(S*n) DP解法已经足够。语言特性在Python中使用for coin in coins:直接遍历列表是高效的。避免在循环内通过索引访问除非有必要。初始化列表时[amount1] * (amount1)是简洁的写法但要记住这创建了一个包含相同引用的列表对于不可变对象如整数没问题。6. 举一反三LeetCode上的变种与扩展掌握基础问题后通过解决它的变种是深化理解的最佳途径。LeetCode上就有几道经典的“找零钱”变种题它们共享核心的DP思想但在状态定义和转移方程上略有不同。6.1 变种一零钱兑换 IILeetCode 518 – 求组合数题目给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0。假设每一种面额的硬币有无限个。分析这和“最少硬币数”问题很像但目标从“求最小值”变成了“求总数”。这立刻让我们联想到背包问题中的“方案数”问题。状态定义dp[i]表示凑成总金额i的硬币组合数。状态转移考虑最后一步使用的硬币。如果最后一步用了面额为coin的硬币那么凑出金额i的组合数就应该加上凑出金额i-coin的所有组合数。所以转移方程是dp[i] dp[i - coin]。关键点遍历顺序这是本题最易错的地方。我们要的是组合数即(1,2)和(2,1)算同一种。为了实现这一点我们必须先遍历硬币物品再遍历金额容量。为什么外层循环遍历硬币意味着我们在逐步考虑“允许使用”的硬币范围。当固定使用前k种硬币时dp[i]表示只使用这前k种硬币凑出金额i的组合数。这样硬币的放入顺序就被固定了不会产生(1,2)和(2,1)这样的重复排列。如果先遍历金额再遍历硬币得到的就是排列数。代码示例def change(amount, coins): dp [0] * (amount 1) dp[0] 1 # 凑成金额0有一种组合什么都不选 for coin in coins: # 先遍历物品硬币 for i in range(coin, amount 1): # 再遍历容量金额 dp[i] dp[i - coin] return dp[amount]6.2 变种二硬币找零的路径记录有时我们不仅需要知道最少硬币数还想知道具体是哪几种硬币。这就需要我们在动态规划的过程中记录“选择”。思路在更新dp[i]时同时用一个额外的choice数组记录是用了哪枚硬币才使得dp[i]变得更小的。初始化choice [-1] * (amount 1)。在状态转移时如果dp[i - coin] 1 dp[i]那么不仅更新dp[i]同时记录choice[i] coin表示凑金额i时最后加入的一枚硬币是coin。计算结束后如果dp[amount]有解则从amount开始反向追踪coin choice[amount]然后amount - coin直到amount为0。收集到的coin序列就是一组最优解可能不唯一此方法找到其中一条路径。代码片段def coinChange_with_path(coins, amount): dp [amount 1] * (amount 1) choice [-1] * (amount 1) # 记录选择 dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i and dp[i - coin] 1 dp[i]: dp[i] dp[i - coin] 1 choice[i] coin # 记录这步选择了哪个硬币 if dp[amount] amount: return -1, [] # 反向构造路径 path [] remaining amount while remaining 0: coin choice[remaining] path.append(coin) remaining - coin return dp[amount], path对于coins[1,3,4], amount6这个函数会返回(2, [3,3])。6.3 思维扩展何时用BFS何时用DP你可能听说过找零钱问题也可以用广度优先搜索BFS来解。思路是将每个金额看作图中的一个节点如果从当前金额cur使用一枚硬币coin能到达新金额nxt cur coin那么就在它们之间连一条边。我们从节点0开始BFS第一次到达节点amount时的路径长度步数就是最少硬币数。BFS解法特点优点在硬币面额很大、目标金额相对不大且最少硬币数本身很小的情况下BFS搜索的层数很浅可能比DP遍历所有状态更快。缺点最坏情况下它需要探索的节点数和DP一样多每个金额都可能被访问并且需要额外的队列和已访问集合的空间。对于金额很大的情况BFS可能因为队列过大而效率低下或内存消耗大。如何选择首选DP动态规划是解决此类“最值”问题的标准且稳健的方法思路清晰代码模板化。除非有特殊理由否则建议使用DP。考虑BFS如果题目暗示或你分析出答案的“深度”即最少硬币数非常小而金额amount很大DP需要填充一个巨大的dp数组这时BFS可能更有优势。例如硬币面额是[1, 1000000]amount999999DP需要计算100万个状态而BFS第二层就能找到解。无论是DP还是BFS其核心思想都是将问题转化为对状态的搜索。DP是自底向上地、系统地计算所有状态BFS是自顶向下地、按层探索状态。理解它们的联系与区别能让你在面对新问题时有更多的武器可以选择。回过头看从贪心算法的直觉尝试到发现其缺陷再到引入动态规划的系统性解法最后扩展到变种问题和不同算法视角我们完成了一次完整的算法思维训练。找零钱问题就像一把钥匙打开的是“最优化问题”这扇大门。真正掌握它不在于背下代码而在于理解状态如何定义、方程如何推导、边界如何处理的思考过程。下次遇到类似问题不妨先问问自己问题的“状态”是什么状态之间如何“转移”想清楚了这些你就能自己推导出解题的框架。 从贪心到动态规划：深入解析找零钱问题与算法设计范式
1. 从一道经典面试题说起为什么找零钱不简单如果你刷过LeetCode或者准备过技术面试那么“找零钱问题”Coin Change绝对是一个绕不开的经典。题目描述通常很简单给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。听起来是不是很像你小时候帮妈妈去小卖部买东西老板找零时的场景但就是这个看似生活化的问题却成了无数程序员面试路上的“拦路虎”。我第一次遇到这个问题时直觉反应就是“贪心”从最大面额的硬币开始拿直到拿不了再换小面额的这不就是现实生活中我们找零的思路吗比如我们有1元、5元、10元要凑18元肯定是先拿一个10元剩下8元拿一个5元最后三个1元。一共5个硬币。这个直觉在硬币面额是“标准”的、成倍数关系时比如我们的人民币体系确实有效。但问题恰恰就出在这里——题目给出的硬币面额是任意的。如果硬币是[1, 3, 4]要凑6元贪心算法会先拿4剩下2元只能用两个1元来凑总共用了3个硬币411。但最优解其实是两个3元硬币只需要2个。看贪心在这里就“贪”错了它只看到了眼前的“最大利益”却可能错过了全局的更优解。正是这个“贪心可能失效”的特性让找零钱问题从一个简单的模拟题升级为了一个必须深入理解算法思想的典型例题。它完美地串联起了“贪心算法”和“动态规划”这两个核心的算法设计范式逼迫我们去思考什么时候可以“贪”什么时候必须“规划”这背后其实是计算机科学中“最优子结构”和“贪心选择性质”这两个核心概念的较量。搞懂了这个问题你不仅会解一道题更能深刻理解一大类组合优化问题的解题思路。接下来我们就先从这个让我们“翻车”的贪心算法开始彻底拆解它的工作原理和致命缺陷。2. 贪心算法的直觉与陷阱为什么“最大面额优先”会失灵当我们面对找零钱问题时大脑的第一反应往往是贪心策略因为它符合我们在现实世界中的经验而且实现起来简单直观。让我们先把这个直觉算法实现出来看看它到底是怎么工作的以及它会在哪里栽跟头。2.1 贪心算法的实现逻辑贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的。对于找零钱问题这个“局部最优”就是当前可用的最大面额硬币。用伪代码来描述这个过程非常清晰将硬币数组coins按面额从大到小排序。初始化一个计数器count 0用于记录硬币总数。遍历排序后的硬币数组当剩余金额amount大于等于当前硬币面额coin时计算最多能使用几枚当前硬币num amount / coin(整数除法)。更新硬币总数count num。更新剩余金额amount - num * coin。遍历结束后检查剩余金额amount是否为0。如果为0返回count。如果不为0说明无法凑出返回-1。用我们之前的人民币例子coins [1, 5, 10],amount 18来走一遍流程排序后为[10, 5, 1]。面对1018 / 10 1拿1个10元count1,amount8。面对58 / 5 1拿1个5元count2,amount3。面对13 / 1 3拿3个1元count5,amount0。成功返回5。结果正确。代码写出来也非常简洁以Python为例def coinChange_greedy(coins, amount): # 从大到小排序 coins.sort(reverseTrue) count 0 for coin in coins: if amount coin: num amount // coin count num amount - num * coin if amount 0: break return count if amount 0 else -1看起来完美无缺效率极高时间复杂度O(n log n)主要是排序之后是O(n)那为什么我们说它有陷阱呢2.2 深入分析贪心失效的根源贪心算法要能获得全局最优解必须满足一个关键性质贪心选择性质。意思是通过局部最优选择每次拿最大硬币能最终构造出全局最优解。这个性质成立需要很强的条件。让我们用反例coins [1, 3, 4],amount 6来深入剖析贪心路径拿4 - 剩2 - 拿1 - 剩1 - 拿1。共3枚硬币 (4,1,1)。最优路径拿3 - 剩3 - 拿3。共2枚硬币 (3,3)。贪心算法在这里为什么错了因为它第一步选择了面额4的硬币。这一步选择看似让剩余金额从6降到了2减少了4是最“贪”的。但正是这一步把后续的可能性给“堵死”了。剩余金额2只能用1元硬币来凑导致总硬币数增多。如果我们不从“拿了什么”看而从“还剩什么”看就能发现动态规划思想的苗头。凑6元的最优解取决于你凑6-coin元需要的最少硬币数再加1。即dp[6] min(dp[6-1], dp[6-3], dp[6-4]) 1 min(dp[5], dp[3], dp[2]) 1。 如果我们知道dp[2]2(11),dp[3]1(3),dp[5]3(41)那么min(3, 1, 2)1 2对应选择面额3的硬币。贪心算法在第一步根本没有去比较dp[2],dp[3],dp[5]这些子问题的解它武断地认为减少的金额最多就是最好的这在不满足“贪心选择性质”的硬币体系下是不成立的。注意一个常见的误解是只要硬币面额是“可整除”的比如12510这种贪心就有效。更准确地说贪心有效的充分条件是硬币体系是“规范”的Canonical Coin System但这需要数学证明。对于任意的硬币组我们无法一眼判断。因此在面试或竞赛中除非题目明确说明硬币面额是标准体系如美元、人民币否则默认贪心策略是不可靠的必须考虑动态规划。2.3 贪心算法的适用场景与教训虽然贪心算法不能解决通用的找零钱问题但它并非一无是处。在满足特定条件的场景下它依然是最高效的解法现实货币系统如人民币1,2,5,10,20,50,100、美元1,5,10,25等这些是设计好的规范体系贪心有效。部分题目约束有些LeetCode变种题会明确说明“你可以认为每种硬币的数量是无限的并且硬币面额是成倍数关系的”这时就可以放心使用贪心。那么从贪心算法的“翻车”中我们能学到什么直觉需要验证编程中直觉很重要但必须用严格的逻辑和反例来验证。遇到最值问题先问自己局部最优一定能导致全局最优吗理解问题本质找零钱问题的本质是“无限背包的最小物品数”问题。这类求“最小值”且物品可无限取用的题目动态规划是更通用的武器。从错误中学习贪心解法的错误恰恰引出了对动态规划的需求。它告诉我们当当前选择会影响未来所有选择时我们需要一个更“聪明”的方法来记住并比较所有可能的选择路径。既然贪心靠不住我们就必须请出更强大的方法——动态规划来系统地解决这个问题。接下来我们将一步步构建出动态规划的解法你会发现它的思路其实非常自然。3. 动态规划的正解构建“最少硬币数”的记忆地图当贪心算法因为目光短浅而失败时动态规划Dynamic Programming, DP提供了一种“高瞻远瞩”的解决方案。它的核心思想不是一次性做出选择而是系统地解决所有更小的子问题并把答案记下来避免重复计算最终组合出原问题的解。对于找零钱问题DP的思路异常清晰和直接。3.1 定义状态与推导状态转移方程这是DP最核心也最关键的一步想清楚了问题就解决了一大半。定义状态我们定义dp[i]表示凑成总金额i所需的最少硬币个数。我们的目标是求dp[amount]。为什么这样定义因为问题问的就是“最少硬币个数”很自然地将答案设为我们状态数组的值。i代表了问题的规模目标金额从0到amount。寻找状态转移方程思考如何从已知的小金额答案推导出大金额的答案。这是DP的精华所在。考虑最后一步假设我们已经凑出了金额i并且最后一步使用了一枚面额为coin的硬币。那么在凑出这最后一枚硬币之前我们已经凑出了金额i - coin。因此凑出金额i的最少硬币数应该是“凑出金额i - coin的最少硬币数”加上这最后一枚硬币也就是加1。但是我们不知道最后一步用的是哪个coin所以我们需要遍历所有可能的、且小于等于i的硬币面额并选择一个使得dp[i - coin] 1最小的那个。由此我们得到著名的状态转移方程dp[i] min(dp[i - coin1], dp[i - coin2], ..., dp[i - coinK]) 1其中coin是所有满足coin i的硬币面额。边界条件Base Casedp[0] 0凑出总金额为0需要0个硬币。这是所有计算的起点。对于无法凑出的金额i我们将其dp[i]初始化为一个很大的数比如amount 1或float(inf)表示“无穷大”或“不可达”。这样在取最小值时这些不可达的状态就不会被选中。3.2 自底向上的迭代实现标准解法有了状态和方程我们可以用迭代填表的方式来实现这是最经典也最易懂的DP实现方式。我们从一个具体的例子coins [1, 3, 4],amount 6来演示这个过程。算法步骤初始化dp数组长度为amount 1因为我们要存从0到amount的所有状态。dp[0] 0其他位置初始化为amount 1一个比最大可能硬币数都大的数这里617。外层循环i从 1 遍历到amount代表我们正在计算凑出金额i的最优解。内层循环遍历coins数组中的每一枚硬币coin。如果coin i说明这枚硬币可以用来凑i则尝试更新dp[i]dp[i] min(dp[i], dp[i - coin] 1)。循环结束后检查dp[amount]。如果它仍然等于初始化的那个大数说明无法凑出返回-1否则返回dp[amount]。手动填表演示初始化dp [0, 7, 7, 7, 7, 7, 7]i1: 硬币1可用。dp[1] min(dp[1], dp[0]1) min(7, 01) 1。dp [0, 1, 7, 7, 7, 7, 7]i2: 硬币1可用。dp[2] min(dp[2], dp[1]1) min(7, 11) 2。dp [0, 1, 2, 7, 7, 7, 7]i3: 硬币1和3可用。用1:dp[3] min(dp[3], dp[2]1) min(7, 21) 3用3:dp[3] min(3, dp[0]1) min(3, 01) 1dp [0, 1, 2, 1, 7, 7, 7]i4: 硬币1, 3, 4可用。用1:dp[4] min(dp[4], dp[3]1) min(7, 11) 2用3:dp[4] min(2, dp[1]1) min(2, 11) 2用4:dp[4] min(2, dp[0]1) min(2, 01) 1dp [0, 1, 2, 1, 1, 7, 7]i5: 硬币1, 3, 4可用。用1:dp[5] min(dp[5], dp[4]1) min(7, 11) 2用3:dp[5] min(2, dp[2]1) min(2, 21) 2用4:dp[5] min(2, dp[1]1) min(2, 11) 2dp [0, 1, 2, 1, 1, 2, 7]i6: 硬币1, 3, 4可用。用1:dp[6] min(dp[6], dp[5]1) min(7, 21) 3用3:dp[6] min(3, dp[3]1) min(3, 11) 2用4:dp[6] min(2, dp[2]1) min(2, 21) 2dp [0, 1, 2, 1, 1, 2, 2]最终dp[6] 2与我们之前分析的最优解两枚3元硬币一致。代码实现Pythondef coinChange(coins, amount): # 初始化dp数组dp[i]表示凑成金额i所需的最少硬币数 # 初始化为一个不可能的大值这里用 amount1因为最多用amount个1元硬币 dp [amount 1] * (amount 1) dp[0] 0 # 金额为0时不需要任何硬币 # 遍历所有金额状态从1到amount for i in range(1, amount 1): # 遍历每一种硬币 for coin in coins: # 如果当前硬币面额小于等于目标金额i则可以考虑使用它 if coin i: # 状态转移dp[i] min(dp[i], dp[i-coin] 1) dp[i] min(dp[i], dp[i - coin] 1) # 如果dp[amount]没有被更新过说明无法凑出 return dp[amount] if dp[amount] ! amount 1 else -1复杂度分析时间复杂度O(S * n)其中S是目标金额amountn是硬币面额种类数。我们需要计算S个状态每个状态需要遍历n种面额来转移。空间复杂度O(S)用于存储dp数组。这个解法是LeetCode上最标准的答案它可靠地解决了所有情况。然而动态规划的魅力不止于此我们还可以从不同的角度来思考这个问题有时能获得一些优化或启发。4. 动态规划的另一种视角完全背包问题如果你对动态规划的分类有所了解可能会认出找零钱问题其实是完全背包问题的一个变种。理解这个视角能帮你把这个问题归类到更广阔的算法知识体系中并借鉴背包问题的优化技巧。4.1 将问题转化为背包模型在背包问题中我们通常有背包容量对应这里的总金额amount。物品对应这里的硬币。每种硬币是一个“物品”。物品重量通常对应物品的“代价”。在这里如果我们把“使用一枚硬币”看作放入背包那么每枚硬币的“重量”就是它的面额coin。物品价值这是我们希望最大化或最小化的目标。在标准的背包问题是最大化价值。在这里我们的目标是“最小化硬币数量”所以我们可以把每枚硬币的价值视为1因为每用一枚硬币总数就加1。那么总价值就是使用的硬币总数我们要做的就是在恰好装满背包总金额等于amount的前提下使得总价值硬币总数最小。物品数量每种硬币有无限个这就是“完全”背包的特点。所以找零钱问题可以精确地描述为一个容量为amount的背包有n种物品硬币每种物品的重量为coins[i]价值为1且每种物品有无限个。求恰好装满背包时最小的总价值是多少如果无法恰好装满返回 -1。4.2 基于背包框架的DP实现与对比在完全背包问题中求“最小价值”的状态转移方程和我们之前推导的完全一致。但背包问题的经典写法内层循环通常是遍历物品硬币外层循环遍历容量金额并且内层循环是顺序遍历这与0-1背包的倒序遍历不同因为物品无限。这种写法有时更符合一些人的思维习惯先决定用哪个硬币再考虑能凑哪些金额def coinChange_pack(coins, amount): dp [amount 1] * (amount 1) dp[0] 0 # 外层遍历物品硬币 for coin in coins: # 内层顺序遍历容量金额因为是完全背包 for i in range(coin, amount 1): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! amount 1 else -1这个版本和之前“先金额后硬币”的版本在时间复杂度上是一样的O(S*n)并且对于找零钱问题两者等价。但在一些变种问题中遍历顺序可能会影响结果比如求组合数还是排列数。对于基础的最小硬币数问题两种顺序都可以。个人经验我刚开始学的时候觉得“先金额后硬币”的写法更直观因为它直接对应着状态转移方程dp[i] min(... dp[i-coin] ...)是在求解一个具体金额i时去尝试所有可能的“最后一步”。而“先硬币后金额”的背包写法更像是在说“引入了这个硬币后对所有能更新的金额状态进行刷新”。在面试中解释第一种通常更容易让面试官理解你的思路。4.3 从背包问题中获得的优化启示虽然基础DP解法已经足够但了解背包问题的优化思路是有益的。例如在完全背包问题中有一种基于“单调队列”的优化可以将时间复杂度优化到 O(S * n) 的理论下界但实现复杂在面试中不常见。更实用的是一些剪枝和常数优化硬币排序与提前终止在开始DP前可以先对coins数组进行排序。在内层循环遍历硬币时一旦遇到coin i因为硬币是升序排列后面的硬币面额更大肯定也大于i所以可以提前break内层循环。这能减少一些不必要的比较。coins.sort() # 排序 for i in range(1, amount 1): for coin in coins: if coin i: # 因为已排序后面的coin都大于i直接跳出 break dp[i] min(dp[i], dp[i - coin] 1)无效状态过滤如果dp[i - coin]是一个不可达的状态即其值等于初始化的最大值那么dp[i - coin] 1也没有意义可以跳过。不过在现代CPU上一次min比较的成本很低显式判断可能并不会带来显著提升有时反而增加分支预测开销。理解背包模型最大的好处是知识迁移。当你遇到“零钱兑换 II”LeetCode 518求凑成总金额的硬币组合数时你会立刻意识到这是完全背包的“组合数”问题状态转移方程从min变成了dp[i] dp[i - coin]并且遍历顺序需要仔细考虑先物品后容量求的是组合数先容量后物品求的是排列数。这种举一反三的能力比死记硬背一道题的解法重要得多。5. 从理论到实战编码细节、测试与常见陷阱掌握了核心算法思想最终还是要落到代码上。在实际编写和调试找零钱问题的DP解法时有几个细节和陷阱需要特别注意这些往往是面试官考察的重点也是新手容易出错的地方。5.1 初始化与边界条件的处理艺术dp数组的初始化看似简单实则暗藏玄机。初始值的选择为什么是amount 1理论上用float(inf)表示正无穷更直观。但在Python中整数运算比浮点数稍快且避免类型转换。amount 1是一个安全的上界因为即使全部用1元硬币最多也只需要amount个。任何有效的解都不会超过这个值。如果最终dp[amount]等于这个值就说明无解。陷阱千万不要初始化为0。因为我们的状态转移是取min如果初始化为0那么所有状态的最小值都会是0结果完全错误。dp[0] 0的重要性这是动态规划的“基石”。它表示凑出金额0需要0个硬币。没有这个定义dp[coin] dp[0] 1这样的转移就无法进行。你可以把它理解为“空集合”是一种合法的解总金额为0时不取任何硬币。金额为0的情况这是一个极易遗漏的边界Case。如果输入的amount就是0根据题目定义凑成总金额所需的最少硬币个数应该返回0因为不需要任何硬币。你的代码必须能正确处理amount 0的情况。在我们的循环中range(1, amount1)在amount0时不会执行dp[0]已经被初始化为0所以最后返回dp[0]即0。但如果你在函数开头没有特殊处理并且后面判断返回值时写成了if dp[amount] amount: return -1当amount0时就会出错因为dp[0]0不大于0。安全的写法是if amount 0: return -1 # 如果题目允许amount为负但通常不会 if amount 0: return 0 # 显式处理0的情况逻辑更清晰 dp [amount 1] * (amount 1) dp[0] 0 # ... DP过程 ... return dp[amount] if dp[amount] amount else -15.2 测试用例设计与调试技巧不要只相信样例自己设计全面的测试用例是写出健壮代码的关键。测试用例描述coinsamount预期结果检查点基础功能[1,2,5]113 (551)验证标准DP贪心失效[1,3,4]62 (33)验证算法正确性非贪心无解情况[2]3-1验证无法凑出时的返回金额为0[1]00验证边界条件大面额硬币[2,5,10]3-1验证小金额无法用大硬币凑包含面额1[1]55验证只有一种硬币硬币包含0[0,1,2]31 (理论上)注意实际题目硬币面额应为正整数此用例用于防御性编程在调试时除了看最终结果打印出整个dp数组是非常有用的手段。它能让你清晰地看到每个子问题的解是如何一步步推导出来的很容易发现状态转移中的逻辑错误。例如对于coins[2], amount3正确的dp数组应该是[0, 3, 1, 3]假设初始化为3。如果你看到dp[1]变成了1那肯定是状态转移的条件if coin i写错了或者没有正确处理无解状态。5.3 易错点与性能考量循环变量与索引在内外层循环中小心混淆i当前金额和coin硬币面额。特别是在状态转移方程dp[i] min(dp[i], dp[i - coin] 1)中确保i - coin作为索引是有效的非负。我们的条件if coin i保证了这一点。空间优化标准的DP使用了 O(amount) 的空间。在某些极端情况下如amount非常大可能会考虑空间优化。由于完全背包问题的状态转移只依赖于上一行如果先物品后容量或当前行左边的状态如果先容量后物品理论上可以优化到 O(amount) 的一维数组我们的写法已经是一维的了。进一步优化空间意义不大。时间优化对于某些特定情况可以提前判断。例如如果硬币面额列表的最小值min(coins) 1那么金额1肯定无法凑出所有不是最小公倍数倍数的金额可能都无法凑出但这属于数学优化通用性不强。在面试中给出标准的 O(S*n) DP解法已经足够。语言特性在Python中使用for coin in coins:直接遍历列表是高效的。避免在循环内通过索引访问除非有必要。初始化列表时[amount1] * (amount1)是简洁的写法但要记住这创建了一个包含相同引用的列表对于不可变对象如整数没问题。6. 举一反三LeetCode上的变种与扩展掌握基础问题后通过解决它的变种是深化理解的最佳途径。LeetCode上就有几道经典的“找零钱”变种题它们共享核心的DP思想但在状态定义和转移方程上略有不同。6.1 变种一零钱兑换 IILeetCode 518 – 求组合数题目给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0。假设每一种面额的硬币有无限个。分析这和“最少硬币数”问题很像但目标从“求最小值”变成了“求总数”。这立刻让我们联想到背包问题中的“方案数”问题。状态定义dp[i]表示凑成总金额i的硬币组合数。状态转移考虑最后一步使用的硬币。如果最后一步用了面额为coin的硬币那么凑出金额i的组合数就应该加上凑出金额i-coin的所有组合数。所以转移方程是dp[i] dp[i - coin]。关键点遍历顺序这是本题最易错的地方。我们要的是组合数即(1,2)和(2,1)算同一种。为了实现这一点我们必须先遍历硬币物品再遍历金额容量。为什么外层循环遍历硬币意味着我们在逐步考虑“允许使用”的硬币范围。当固定使用前k种硬币时dp[i]表示只使用这前k种硬币凑出金额i的组合数。这样硬币的放入顺序就被固定了不会产生(1,2)和(2,1)这样的重复排列。如果先遍历金额再遍历硬币得到的就是排列数。代码示例def change(amount, coins): dp [0] * (amount 1) dp[0] 1 # 凑成金额0有一种组合什么都不选 for coin in coins: # 先遍历物品硬币 for i in range(coin, amount 1): # 再遍历容量金额 dp[i] dp[i - coin] return dp[amount]6.2 变种二硬币找零的路径记录有时我们不仅需要知道最少硬币数还想知道具体是哪几种硬币。这就需要我们在动态规划的过程中记录“选择”。思路在更新dp[i]时同时用一个额外的choice数组记录是用了哪枚硬币才使得dp[i]变得更小的。初始化choice [-1] * (amount 1)。在状态转移时如果dp[i - coin] 1 dp[i]那么不仅更新dp[i]同时记录choice[i] coin表示凑金额i时最后加入的一枚硬币是coin。计算结束后如果dp[amount]有解则从amount开始反向追踪coin choice[amount]然后amount - coin直到amount为0。收集到的coin序列就是一组最优解可能不唯一此方法找到其中一条路径。代码片段def coinChange_with_path(coins, amount): dp [amount 1] * (amount 1) choice [-1] * (amount 1) # 记录选择 dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i and dp[i - coin] 1 dp[i]: dp[i] dp[i - coin] 1 choice[i] coin # 记录这步选择了哪个硬币 if dp[amount] amount: return -1, [] # 反向构造路径 path [] remaining amount while remaining 0: coin choice[remaining] path.append(coin) remaining - coin return dp[amount], path对于coins[1,3,4], amount6这个函数会返回(2, [3,3])。6.3 思维扩展何时用BFS何时用DP你可能听说过找零钱问题也可以用广度优先搜索BFS来解。思路是将每个金额看作图中的一个节点如果从当前金额cur使用一枚硬币coin能到达新金额nxt cur coin那么就在它们之间连一条边。我们从节点0开始BFS第一次到达节点amount时的路径长度步数就是最少硬币数。BFS解法特点优点在硬币面额很大、目标金额相对不大且最少硬币数本身很小的情况下BFS搜索的层数很浅可能比DP遍历所有状态更快。缺点最坏情况下它需要探索的节点数和DP一样多每个金额都可能被访问并且需要额外的队列和已访问集合的空间。对于金额很大的情况BFS可能因为队列过大而效率低下或内存消耗大。如何选择首选DP动态规划是解决此类“最值”问题的标准且稳健的方法思路清晰代码模板化。除非有特殊理由否则建议使用DP。考虑BFS如果题目暗示或你分析出答案的“深度”即最少硬币数非常小而金额amount很大DP需要填充一个巨大的dp数组这时BFS可能更有优势。例如硬币面额是[1, 1000000]amount999999DP需要计算100万个状态而BFS第二层就能找到解。无论是DP还是BFS其核心思想都是将问题转化为对状态的搜索。DP是自底向上地、系统地计算所有状态BFS是自顶向下地、按层探索状态。理解它们的联系与区别能让你在面对新问题时有更多的武器可以选择。回过头看从贪心算法的直觉尝试到发现其缺陷再到引入动态规划的系统性解法最后扩展到变种问题和不同算法视角我们完成了一次完整的算法思维训练。找零钱问题就像一把钥匙打开的是“最优化问题”这扇大门。真正掌握它不在于背下代码而在于理解状态如何定义、方程如何推导、边界如何处理的思考过程。下次遇到类似问题不妨先问问自己问题的“状态”是什么状态之间如何“转移”想清楚了这些你就能自己推导出解题的框架。