从一道最少硬币题开始聊聊动态规划到底在干什么今天是我算法学习打卡的第44天前阵子一直在跟贪心、回溯、搜索这些“偏策略”的算法打交道今天正式进入动态规划这个大名鼎鼎的领域。说实话动态规划这四个字我在网上看了不下十遍——有人叫它DP有人喊它“状态转移大法”还有人直接说“想不明白就背模板”。但在真正动手做了一天题之后我的感受是动态规划不是一种具体的算法而是一种思考问题的方式。今天这天的学习路线是从最少硬币问题切入理解“状态”“转移”“最优子结构”这几个核心概念然后上手01背包最后把动态规划和贪心、递归做了个对比总结。这篇文章不是我抄什么题解整理出来的而是把我从“看到题目一脸懵”到“能自己写出状态转移方程”的全过程包括中间的思路卡壳、踩坑和调试记录完整记录下来。如果恰好你也卡在动态规划入门这个坎上这篇内容应该能帮你在思路层面捅破那层窗户纸。1. 动态规划到底是个啥先忘掉“状态转移方程”这六个字1.1 从暴力递归说起为什么重叠子问题这么关键很多人第一次接触动态规划上来就甩给你一个dp数组、一个状态转移方程然后让你背。这其实是完全错误的学习路径。我自己的理解方式是倒退回去先看一个最简单的例子计算斐波那契数列的第n项。教科书会告诉你F(n)F(n-1)F(n-2)这本身就是一个递归过程。但如果你画一下递归树你会发现F(5)要算F(4)和F(3)而F(4)又要算F(3)和F(2)——同一个子问题被反复计算了无数遍。这种“大问题拆成小问题小问题又互相重叠”的结构就是动态规划能起作用的前提。所以学动态规划的第一步是识别一道题能不能用动态规划来解。判断标准有两条一是有没有重叠子问题二是有没有最优子结构。什么叫最优子结构简单说就是整个问题的最优解可以由子问题的最优解推导出来而不是需要另起炉灶重新计算。我记得本科时有一次面试面试官问我的问题是“动态规划和分治算法的区别是什么”我当时答得磕磕绊绊。现在回头看答案其实很清晰——分治算法比如归并排序把问题拆成互不相交的子问题分别解决后合并而动态规划面对的子问题之间是有交集的既然是交集就可以用一张表把这些中间结果记录下来避免重复计算。1.2 状态、转移、边界入门动态规划的三个核心要素在真正写代码之前我建议你先建立一套自己的分析框架。我按照网上的教程加上自己的调试经验总结出一套万能的“三步走”第一步定义状态。状态就是你用什么东西来描述当前所处的情况。比如最少硬币问题里dp[i]可以定义为“凑出金额i所需的最少硬币数”这里i就是状态变量。第二步写状态转移方程。也就是思考当前这个状态是怎么从之前的状态变过来的还是以硬币问题为例dp[i]应该等于dp[i - coin] 1对每个面额的硬币取最小值。这一步是整个动态规划的核心也是最难的部分后面我会专门展开讲。第三步确定初始化和遍历顺序。边界条件决定了递归或循环的起点遍历顺序则决定了你在计算某个状态时它依赖的状态是否已经被算出来了。这三个要素正好对应了动态规划题解里最常见的三段式代码结构——初始化dp数组、循环计算、返回答案。初学者一开始不用急着理解所有细节先照着这个框架去套题套多了自然就有感觉了。1.3 记忆化搜索和自底向上动态规划的两种打开方式我第一天学动态规划发现同一个题解里有的人写递归备忘录有的人写for循环数组结果还是一样的。这里需要搞明白动态规划有两条技术路线自顶向下记忆化搜索和自底向上表格递推。自顶向下比较好理解就是写递归函数但是用一个memo数组把算过的结果存下来下次直接用。这种方式符合人脑的直觉代码也容易写缺点是递归有栈溢出风险尤其是数据量大的时候。自底向上则是反过来从最小的子问题开始用循环一点点推到目标问题。代码性能稳定但思维方式和递归不同需要你先想清楚所有可能的状态然后按顺序填表。很多入门教程只讲自底向上这一种让人误以为动态规划必须用数组加循环。实际上我在做最少硬币问题的时候就是先写了递归版本来验证状态转移方程是否正确再改成循环版本去提交这样做正确率会高很多。2. 经典入门题实战最少硬币问题全解析2.1 题目描述和第一直觉一个典型的错误思路先看今天的第一个例子可以说是动态规划界的“hello world”——最少硬币问题。题目很简单给定一堆不同面额的硬币比如1元、3元、5元以及一个目标金额比如11元问你凑出这个金额最少需要多少枚硬币如果凑不出来就返回-1。我第一次拿到这个题第一反应是——这不就是贪心吗先把大面额硬币往死里用不够了再用小面额补齐。比如11元先用5元硬币用两个还剩1元再用一个1元硬币总共3枚完美。在硬币面额是1、3、5的情况下贪心确实能凑出正确结果。但问题是如果硬币面额变成2、5、7目标金额是11呢贪心会先用两枚5元剩1元发现凑不出来于是宣告无解。可实际上5222等于11需要4枚硬币是有解的。所以贪心算法依赖硬币面额的特定性质而动态规划不需要这种依赖它通过穷举所有组合来保证找到最优解。这个反例就是我开始理解“动态规划为什么比贪心更通用”的起点。2.2 从递归到记忆化再到递推的完整推导那动态规划怎么做我还是按照上一节的三步走来推导。第一步定义状态。我用dp[i]表示“凑出金额i需要的最少硬币数”。如果i等于0那当然一枚硬币都不用所以dp[0]0。第二步写状态转移方程。凑出金额i最后一步一定是放了一枚面额为c的硬币那么之前的金额是i-c对应的最少硬币数就是dp[i-c]再加1就是当前这枚。对所有硬币面额遍历取最小值就行dp[i] min(dp[i - c] 1) 对所有满足 c ≤ i 的硬币面额c第三步确定初始化和遍历顺序。dp[0]0其他值先初始化为一个大数比如inf然后从i1一直算到iamount。按照这个思路我写出来的核心代码长这样def coinChange(coins, amount): # 初始化dp数组长度为amount1全部填充一个大数 dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! float(inf) else -1这里有个细节我想多说两句初始化时为什么用inf而不是-1因为dp[i]的语义是“凑出金额i的最少硬币数”在还没有计算出结果之前它处于“未知”状态而“未知”对于min操作来说应该被当作正无穷来处理这样任何有效值都能覆盖它。如果用-1初始化min的时候就会永远取到-1逻辑就全错了。2.3 复杂度分析和为什么“最少硬币数”能拆成子问题这个代码的时间复杂度是O(amount * len(coins))空间复杂度是O(amount)。注意amount可以是几千甚至几万这个复杂度是完全能接受的。但代码能跑对不代表你理解了为什么能这么拆。我那天想了很久最终用一个生活化的类比说服了自己你要从地面爬到第100级台阶一次可以跨1级或者2级问最少跨几次。你不用从第0级开始模拟每一级怎么踩你只需要知道爬到第100级的最后一步要么是从第99级跨1级上来的要么是从第98级跨2级上来的。所以f(100) min(f(99), f(98)) 1。硬币问题同理。凑出11元的最后一步要么放了一枚5元前面凑6元要么放了一枚3元前面凑8元要么放了一枚1元前面凑10元所以dp[11] min(dp[6], dp[8], dp[10]) 1。这就是把大问题拆成小问题的本质——永远只关注最后一步发生了什么。想通了这一点之后遇到再复杂的动态规划题我都能快速找到切入点。3. 进阶必考题01背包问题的思路拆解3.1 从“选还是不选”的角度理解背包问题最少硬币问题算是热身今天真正让我卡了快两个小时的是01背包问题。题目描述很朴素有一个容量为W的背包有n件物品每件物品有重量w[i]和价值v[i]问你最多能装下多大价值的东西。为什么叫“01”因为每件物品只有两种选择装进去1或者不装0不能装一半也没有“无限件”。这个问题看似和硬币问题很像但有个关键区别硬币问题不限制硬币数量而背包问题的每件物品只有一件。所以硬币的dp[i]循环一遍就行而背包的循环顺序有讲究一不留神就会把同一件物品用无数次变成完全背包问题。我第一次写背包代码就直接套了硬币的模板结果答案大得离谱。后来查了半天才知道01背包需要倒序遍历容量目的就是为了保证每件物品只被使用一次。3.2 二维dp和一维滚动数组的演变过程先看最基础的二维dp版本。定义dp[i][j]为“考虑前i件物品背包容量为j时能装下的最大价值”。那么对于第i件物品有两种情况不装dp[i][j] dp[i-1][j]装前提是j w[i]dp[i][j] dp[i-1][j-w[i]] v[i]两者取最大值。伪代码是for i in range(1, n 1): for j in range(W 1): if j w[i]: dp[i][j] dp[i-1][j] else: dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这个版本空间复杂度是O(n*W)如果n和W都到几千内存就爆了。所以需要优化成滚动数组也就是只保留一维每次更新时覆盖旧值。但这里有一个最大的坑j必须从大到小遍历。dp [0] * (W 1) for i in range(1, n 1): for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])我一开始完全不能理解为什么要倒着来后来自己手算了几个值才明白正序遍历时dp[j-w[i]]可能已经在当前这轮循环中被更新过了那它代表的就是“已经装了当前物品”的状态相当于同一件物品被重复装了好几次。而倒序遍历时dp[j-w[i]]还是上一轮的值也就是还没装当前物品的旧状态这样才符合01背包“每件最多一次”的约束。3.3 一个实例演练容量10的背包四件物品怎么装光说理论容易飘我那天用一个具体例子手算了一遍才算彻底放心。假设背包容量W10四件物品如下物品编号重量w价值v123234368445按一维dp倒序遍历第一轮处理物品1w2,v3dp[10到2]会变成3。第二轮处理物品2w3,v4当j10时dp[10]max(dp[10], dp[7]4)7含义是物品1加上物品2总价值7。第三轮处理物品3w6,v8j10时dp[10]max(7, dp[4]8)11这代表物品1(3)加物品3(8)总价值11。最后处理物品4可以验证最优解是物品2物品3价值4812重量369没有超过10。手算完这个例子之后我终于有一种“哦原来这个表是这么填出来的”的感觉。所以我强烈建议初学者遇到背包类问题别急着写代码先在纸上把dp表画出来一格一格填一遍填完之后你对“状态转移”四个字的理解会完全不一样。3.4 01背包的常见变体恰好装满和最大容量01背包还有一个很容易在题目里踩到的变体问的不是“最多能装多少价值”而是“能不能恰好装满指定容量”。这种情况下dp数组的初始化就不能全为0了而是要改成dp[0]0其他为-inf或者-1表示“无法恰好装满”。我自己的理解是“最多装多少”是允许剩余容量闲置的所以任何容量初始都是0什么也不装就是合法方案而“恰好装满”要求每一格容量都被用到所以除了容量0其他容量在没有合法方案前都是“不可达”的。这两种初始化方式直接决定了dp数组的语义。以后做题时第一件事就是仔细看题目要求的是“最大价值”还是“恰好装满”这决定了初始化的写法。4. 动态规划vs贪心vs回溯三兄弟的适用边界4.1 拿跳跃游戏II当试金石学了一天动态规划之后我回头看之前做过的一道题——跳跃游戏II发现这道题完美地展示了动态规划和贪心的区别。题目是给定一个非负整数数组每个数字表示你在该位置可以跳跃的最大长度问最少跳几次能跳到最后一个位置。我当初是用贪心做的每次在当前可到达范围内选择一个能跳得最远的位置然后跳过去。这个思路是对的因为这道题有一个隐藏性质——跳跃次数是单调的能跳过去的情况只需要尽量往前走就行贪心不会错过全局最优。但如果把题目稍微改一下问你“跳到最后一个位置有多少种不同的跳跃方式”贪心就彻底废了。因为这个问题需要把所有可能性都数出来必须用动态规划dp[i]表示跳到位置i的方式总数dp[i] sum(dp[j])对所有能从j跳到i的j求和。你看同样是跳跃游戏一个贪心能解决一个必须上DP原因就是前者只需要局部最远后者需要统计全局路径。这说明了一个道理贪心是一种“短视”策略它的正确性必须有严格的数学证明作为支撑而动态规划是一种“全知”策略它通过枚举所有状态来保证全局最优。能用贪心就优先用贪心因为时间复杂度低、代码简单但贪心失效时动态规划是更稳妥的后手。4.2 记忆化搜索和回溯剪枝的本质差异还有一个我容易混淆的概念是动态规划尤其是记忆化搜索和回溯剪枝到底有什么区别回溯搜索的典型场景是全排列、N皇后这类问题它的本质是深度优先遍历所有可能的解遇到不满足条件的就剪枝。在这个过程中同一个子问题可能会被重复计算多次但没有办法直接改成一个“查表”的写法因为你关心的是所有解的结构而不是某个数值的最优值。而动态规划面对的是一个“最优化问题”或者“计数问题”答案是一个数。既然只是一个数就可以记录下来供后续状态复用。从这个角度说动态规划是“有记忆的回溯”——它把重复计算的子问题结果缓存下来从而把指数级的时间复杂度降为多项式级。我自己的做题经验是拿到一道题先看它要什么。如果要的是“所有可行方案”那大概率是回溯如果要的是“最少次数/最大价值/方案总数”那大概率是动态规划。这个判断方法虽然不是100%精确但作为第一直觉非常管用。4.3 动态规划的优化方向状态压缩和空间优化聊完和其他算法的对比再回到动态规划本身。今天我在写代码时发现就算你状态转移方程写对了代码也未必能跑过大数据量因为空间复杂度可能会爆。比如二维dp的O(n*W)n和W稍微大一点就直接内存溢出了。常见的优化思路有两种。第一种是滚动数组/一维化就像01背包那样把二维dp压缩成一维因为当前行只依赖上一行的值更早的值就没用了。第二种是状态压缩DP用在“棋盘覆盖”“旅行商”这类题目中把某个维度的状态编码成一个二进制整数从而把所有状态压缩到一个数组里。这种方法有点难但它会打开动态规划的另一个世界我打算后面专项去啃。我的建议是入门阶段先别追求花哨的优化老老实实把二维dp写对再去学空间压缩。因为我踩过的坑是——用一维滚动数组写错之后很难调试因为不知道是状态定义错了还是遍历顺序错了。二维版本虽然占用空间大但每个值都对应一个明确含义查错容易得多。5. 动态规划刷题时的几个高频坑点5.1 初始化错误inf和-1的选择在入门动态规划的前两周我几乎每一次WAWrong Answer都出在初始化上。最常见的问题就是把dp数组初始化为0或-1导致状态转移方程的结果被污染。这里我总结出一个经验法则如果你的状态是“最小值/最少次数”其他状态必须初始化为一个大数inf如果你的状态是“最大值/最大价值”其他状态可以初始化为0。但是如果题目要求“恰好装满”初始化规则会变——除了dp[0]其他要初始化为负无穷或-1同时更新时要判断前一个状态是否可达。这个规则不背下来光靠临场推理很容易出错。5.2 遍历顺序正序和倒序的永恒谜题今天做01背包被遍历顺序折磨得不轻。我后来整理了一套“判断帽子戏法”01背包容量从大到小遍历防止同一物品被重复使用完全背包每件物品可以无限用容量从小到大遍历允许覆盖当前物品的新状态二维dp遍历顺序通常无所谓因为当前格子的更新依赖的是上一行的值不会冲突这套规律不是死记硬背而是理解了“dp[j-w[i]]代表的是旧状态还是新状态”之后自然得出的。我建议你亲自跑一个正序和倒序的对比测试观察输出差异那种“哦原来差在这里”的感觉比看十篇教程都管用。5.3 状态定义不清导致转移方程写不出来还有一种情况是——dp数组的语义没定义对导致方程怎么都写不顺畅。比如“最长递增子序列”这道题dp[i]如果定义成“前i个元素的最长递增子序列长度”你很难写出转移方程但如果你把它定义为“以第i个元素结尾的最长递增子序列长度”转移就自然了dp[i] max(dp[j] 1)对所有满足j i且nums[j] nums[i]的j。所以我建议在动笔之前先花五分钟把状态定义写清楚想清楚dp[i]到底“代表什么含义”“下标的范围是多大”“最终答案怎么取”。这三个问题想明白了代码基本就水到渠成了。状态定义是所有动态规划题里最重要的一步也是稍纵即逝的灵感建议想明白后立刻记下来。6. 我的动态规划学习方法和工具推荐6.1 如何用纸笔推导一份“状态转移图”我给所有初学者的第一个建议就是买一叠A4纸或者开一个画板App遇到动态规划题先画状态转移表再写代码。不要一上来就打开编译器。比如做最少硬币问题时我会把amount从0到11的格子全部画出来然后一个硬币一个硬币地去填。填的过程中我会发现有些值会反复被更新有些则一次到位。这个“填表”的过程就是你在建立“状态”和“转移”的直觉。到了01背包我会把物品编号作为行、容量作为列画一个n行W列的表格然后一行一行地填。填完之后我甚至能指出“最优解是由哪几个格子路径组成的”。这个能力在面试时非常加分因为面试官看到你能手动推导状态转移就知道你不是在背模板。6.2 从刷题网站到调试技巧我的实操工具清单如果你跟我一样是自学我建议准备三样东西LeetCode或者类似OJ平台动态规划的题量很大按照“入门-背包-序列型-区间型”的顺序刷题每天3-5道即可本地Python环境不要只在网页上写代码本地环境方便你打印dp表调试。我常用的调试手段是在循环里打印整个dp数组看每个状态在每一轮之后长什么样一个记录模板的笔记工具不是让你背模板而是记录“哪种题型对应哪种状态定义和遍历顺序”。我会把每道题的关键状态定义、转移方程、初始化方式、复杂度记下来形成一个自己的速查手册这里特别推荐一个调试技巧在循环里加一行print(dp)观察每一轮结束后的dp数组值。很多动态规划题的错误一眼就能看出来——比如某个值突然变得离谱大那一定是初始化或者遍历顺序出了问题。6.3 适合新手的第一组动态规划题目单最后我把自己刷过的、认为最适合新手的动态规划题目单整理一下按难度递增排列爬楼梯入门状态转移打家劫舍一维dp经典最长递增子序列状态定义技巧最少硬币完全背包思想01背包滚动数组遍历顺序分割等和子集01背包变体最长公共子序列二维dp编辑距离高难度综合我个人是从第1题开始刷到第4题时就有一种“好像摸到门道了”的感觉到第6题时已经能独立写出转移方程。如果你也正在这个阶段不用急一天搞懂一题比一天刷十题但什么都不懂要强得多。7. 一点个人心得别怕“想不明白”它只是个过程今天day44的学习最大的收获并不是我掌握了多少种动态规划的套路而是我终于接受了一个事实动态规划的“状态”不是靠看出来的是靠大量的试错和推导磨出来的。我在学习过程中经常遇到一种情况——状态转移方程怎么都写不出来或者写出来了但过不了样例。以前我可能会烦躁、怀疑自己智商不够但现在我明白了这不是智商问题而是“思维肌肉”还没练出来。每卡一次壳其实都是在强化对状态和转移的理解。如果你也正在被动态规划折磨我的建议很简单先别追求最优解先把一个能跑的朴素版本写出来哪怕空间复杂度爆炸哪怕是递归备忘录都没关系。能跑通就已经比“只会空想”强了几个层次然后再一步步优化。这个过程可能很慢但它绝对值得。动态规划这东西你只要熬过前面最黑暗的一周后面每做一道新题都会有“原来如此”的爽感。