★ FEATURED ARTICLE 坚持到 day33动态规划 part06这个进度条本身就说明你已经熬过了从 0 到 1 的阶段。前五天你在斐波那契、爬楼梯、不同路径这类线性递推题上反复练习基本能闭眼写出转移方程于是第六天开始接触真正的硬核主题背包问题、多状态决策、滚动数组这些让人既兴奋又头大的内容。然后你会发现一个扎心的事实——模板背得再熟题目稍微变一变照样不会写。这个现象并不是你笨而是动态规划学到这里正在从“套公式”转向“建模思维”。day33 这个节点我当年也是在这个阶段卡了很久回头复盘才发现真正拉开差距的不是刷题数量而是对状态定义和转移方向的理解深度。这篇文章就围绕动态规划 part06 这个阶段的典型内容展开顺便把几个相关热搜词说透KMP 到底算不算动态规划、01 背包的模板为什么必须倒序遍历、动态规划建模思维到底怎么练。看完之后你会发现part06 不是一道坎而是一个真正入门的分水岭。1. 练到 part06 还没开窍不是题量不够是建模思维没有落地动态规划这门课很多人刷到第六天很容易产生一种“似懂非懂”的感觉看题解特别顺畅每一步都合理关上答案自己写却什么都憋不出来。其实问题出在一个非常底层但常被忽略的动作上——建模。1.1 动态规划的第一步永远是状态定义我见过太多人一上来就默写模板结果题目一变就崩。根源在于他们跳过了最关键的一步没有用一句清晰的话把 dp 数组的含义讲明白。拿最经典的硬币找零举例。同样是“给定硬币面额和目标金额”你可以定义 dp[i] 表示“凑出金额 i 的最少硬币数”也可以定义 dp[i] 表示“凑出金额 i 的方案总数”。这两个定义看着都合理但转移方程完全不同如果 dp[i] 是“最少硬币数”转移是dp[i] min(dp[i], dp[i - coin] 1)如果 dp[i] 是“方案总数”转移是dp[i] dp[i - coin]。这两种写法拿到代码里只差一个 min 和加号的区别但含义天差地别。很多人最后 WA 了又 WA发现自己连“这题到底问什么”都没想清楚就急着写循环。这是动态规划的第一大杀手。我自己的习惯是每次做题第一行先写注释把状态定义完整写出来。比如在编辑距离里我会写“dp[i][j] 表示 word1 的前 i 个字符变成 word2 的前 j 个字符所需的最少操作数”。一旦这句话写清楚了后面分析转移其实就是围绕这句话展开的最后一步是增、删、改还是不动从哪个状态来状态定义没有歧义转移方程才不会走偏。1.2 判断一道题该不该用 DP三个信号还有一个高频困惑是拿到题根本没有“这是动态规划”的意识非要等看完题解才恍然大悟。要解决这个问题你得建立一套判断机制。以我的经验一道题适合用动态规划通常同时具备三个特征。第一重叠子问题。把问题暴力递归展开时同一个子问题会被反复计算很多次。斐波那契就是一个最典型的例子fib(5)要递归计算fib(4)和fib(3)而fib(4)又要算fib(3)整个递归树里有大量重复节点。动态规划的核心目标之一就是把这些重复计算缓存起来。第二最优子结构。原问题的最优解可以由子问题的最优解组合而来。比如 01 背包中容量为 V 时的最优值要么来自不放第 i 件物品时的状态要么来自“容量为 V - w[i] 时的最优值再加第 i 件物品的价值”。子问题独立、最优能拼接才符合动态规划的使用条件。第三无后效性。这是很多人忽略的一点。意思是一旦某个状态确定了之后怎么发展只和这个状态本身有关而和“如何到达这个状态”的路径无关。可以把它类比成打牌你只关心手里现在这副牌至于这副牌是上一局赢来的还是输来的对下一局没有任何影响。如果问题里存在“走过的路线会影响后续选择”这种强依赖通常需要加维度或者干脆换算法。这三条信号在我练 part06 之前只是当口诀背直到开始做背包才发现它们是真能用的判断工具。比如看到“一个物品只能选一次”我立刻想到这不就是 0/1 决策每个物品只有选和不选两种可能选完就消耗容量这是背包模型的味道。1.3 第六天会遇到的认知断层线性 DP 和背包 DP 之间有一个很容易让人崩溃的跨度。前几天的题比如爬楼梯、最大子序和状态基本是一维的dp[i] 只依赖 dp[i-1]、dp[i-2] 这种固定邻居。到了 part06一下子冒出来二维数组、三层循环、滚动数组很多人的第一反应就是“我是不是少学了什么”。其实不是少学了而是动态规划的训练开始从“递推”进入了“决策模型”阶段。线性递推更像是在走一条直线每一步只有一个方向而 01 背包、完全背包、多重背包这类问题难点在于每个物品都携带一个“拿/不拿”或者“拿几个”的决策开关所有决策叠加在一起还要满足容量约束。这时候状态必须增加一个维度来记录“已经考虑到了第几个物品”也就是 dp[i][j] 的来历。所以如果你在 part06 感到吃力不用怀疑自己菜。这种认知断层几乎人人都会经历关键是别急着灌新题把背包问题背后的“遍历顺序”和“状态定义”吃透比多做十道题都管用。2. Part06 阶段真正在练什么背包模型与遍历顺序的底层逻辑如果说动态规划前面几天是在熟悉“状态转移”的形式那 part06 基本就是把你按在背包问题上反复摩擦。因为背包问题太经典了它几乎是所有多阶段决策问题的雏形有约束、有取舍、有价值最大化目标。这一节我把 01 背包和完全背包的底层逻辑拆开讲清楚。2.1 01 背包先把二维转移写明白先看标准问题有 n 件物品第 i 件物品的体积是 w[i]价值是 v[i]背包总容量为 V每件物品最多只能用一次问能装入背包的最大总价值是多少。我第一次学的时候一上来就背一维数组模板结果完全不知道代码在干嘛。后来老老实实从二维开始推才真正打开任督二脉。二维定义是这样的dp[i][j]表示“只考虑前 i 件物品背包容量为 j 时能获得的最大价值”。注意这里“前 i 件物品”意味着我们已经替系统做出了前 i 个决策只差第 i 件物品还没最终决定。对第 i 件物品只有两种选择不选那么容量 j 不变价值就是dp[i-1][j]选前提是容量够即j w[i]此时价值是dp[i-1][j-w[i]] v[i]。所以转移方程写成dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]);这个方程的意思是第 i 件物品的价值和体积已经知道我只需要在上一个阶段只考虑前 i-1 件的基础上做一次“贪心式比较”取价值更大的方案。二维写法虽然空间大但逻辑非常直观特别适合用来做状态表的手推练习。我强烈建议 part06 的初学者先不要碰一维版本拿个小例子把二维表一行一行填出来比看十篇题解都有效。你会在填表过程中看到每一行的值都是从上一行某个格子“平移”或“跳转”过来的。这种视觉记忆比抽象理解牢固得多。2.2 一维滚动数组为什么要倒序遍历二维空间是O(n*V)当 n 达到几千、V 达到几万时内存很容易爆。于是大家引入滚动数组优化把二维压成一维核心思想是第 i 轮计算只依赖第 i-1 轮的数据没必要把之前所有轮次都留在内存里。一维模板长这样vectorint dp(V 1, 0); for (int i 1; i n; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }很多新手会问这个内层循环为什么要从大到小、倒着遍历不能和完全背包一样正着写吗答案就藏在“dp[j] 到底代表当前第几轮的数据”里。如果用一维数组表示二维状态那么内层循环每执行一次dp 数组里的值就会被更新一批。如果正序遍历当 j 从小到大走时dp[j - w[i]]可能已经被本轮更新过也就是说这个值已经是“考虑过当前第 i 件物品之后的结果”了。此时再去更新dp[j]等于把同一件物品用了两次就违背了“每件物品最多用一次”的约定。反过来倒序遍历时dp[j - w[i]]一定还停留在上一轮 i-1 的状态还没有被本轮覆盖所以用它来更新dp[j]就保证第 i 件物品只被考虑了一次。一句话总结01 背包一维写法必须倒序遍历倒序的本质是防止本轮更新覆盖掉上一轮还需要的数据。这个点是我当年拍大腿才想明白的也特别建议大家遇到背包题时先二档确认“我是 01 背包还是完全背包遍历顺序对不对”这个习惯能帮你避开大量隐藏 bug。2.3 完全背包改一个方向等于换一道题完全背包和 01 背包唯一的模型区别是每件物品可以无限次取用。代码上的变化更是小到令人发指——内层循环从倒序改成顺序即可vectorint dp(V 1, 0); for (int i 1; i n; i) { for (int j w[i]; j V; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }为什么正序就对了因为正序遍历时dp[j - w[i]]已经被本轮更新过里面可能已经包含了一个或多个当前物品 i。你一看到“可能包含了当前物品”就该反应过来这不就是允许重复选同一个物品了吗完全背包要的就是这个效果。这里有一个特别容易踩坑的细节很多人走到完全背包求方案数时又开始懵。如果你要求“有多少种方法正好装满背包”且区分物品的选择顺序比如排列算不同方案和组合算一种方案时遍历顺序的讲究更多要求组合数不考虑顺序外层循环物品内层循环容量要求排列数不同顺序算不同方案外层循环容量内层循环物品。这个规则我记得特别牢因为踩过一次大坑零钱兑换 II 那道题我只改了一层循环顺序答案直接从对变成错后来查资料才明白外层容量时dp[3]会被币种 1、2 以不同顺序重复计数正好满足排列数的需求。part06 阶段如果把这一点搞清楚后面遇到零钱兑换、单词拆分这类题会轻松很多。2.4 状态压缩与中间状态调试滚动数组是背包问题的重要优化手段但代价是你失去了完整的状态历史。二维数组可以随时回溯“第 i 件物品到底选了没有”一维滚动数组做不到因为每一轮的数据都被覆盖了。所以如果你后续遇到要求输出具体方案的题目比如“请输出装入背包的物品编号”那就不能直接用一维滚动数组全程压缩要么保留二维数组要么额外开一个choice[i][j]记录决策来源。调试背包问题时我有一个用了很久的技巧用小数据规模把整个 dp 表打印出来。比如一组简单物品一件体积 1 价值 15一件体积 2 价值 20包容量 5你手动填一次二维表再在代码里加个二维数组输出能一眼看出哪些转移是对的哪些格子算错了。这个过程非常枯燥但对建立“动态规划状态变化”的手感特别有效part06 阶段值得安排一次。3. 碰上一个热搜问题KMP 算法到底属于动态规划吗搜索动态规划相关内容时你大概率会刷到一个很热闹的问题KMP 算法属于动态规划吗看起来是个概念问题但它能帮我们反过来检验自己对动态规划的理解是不是够深。3.1 为什么有人会把 KMP 和 DP 混在一起KMP 字符串匹配算法里有一个非常核心的前缀函数也就是 next 数组它的计算过程长这样vectorint prefixFunction(string s) { int n s.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) { j pi[j - 1]; } if (s[i] s[j]) { j; } pi[i] j; } return pi; }从形式上pi[i]的计算用到了pi[i-1]甚至还有pi[j-1]这种跳转看起来特别像状态转移当前值由前一个状态推导而来。于是很多人就想当然地觉得“这里用了前一个状态的结论所以 KMP 有动态规划思想”。再加上市面上有些文章会用“动态规划求 next 数组”作为标题动态规划这个词被随意扩展后KMP 被归入 DP 也就不奇怪了。3.2 从三个维度拆开对比要回答这个问题不能只看“有没有用到之前算的结果”而要看问题的本质结构。我整理了三个维度的对比对比维度KMP 前缀函数经典动态规划目标匹配模式串与前缀求最长相等前后缀长度不是求最优值求最大/最小/方案数/可行性等最优解或统计解核心结构模式串自身的局部对称性质扫描过程没有“选择/不选择”的二分决策有明确决策如选或不选、走哪个方向、划分方式子问题关系主要依赖前一个位置的函数值逻辑是“匹配失败就回退”本质类似自动机状态转移强调重叠子问题和最优子结构子问题之间有大量重叠且需要比较典型代码特征while 回退不是遍历所有状态而是直接跳到可匹配的位置通常嵌套循环遍历所有状态空间并做 max/min/累加从这个对比能看出KMP 的 next 数组计算是一种递推递推的外表和 DP 有相似之处但它没有“在多个决策中挑最优”的过程也没有“价值函数”的概念。它更像一个确定性的有限状态自动机当前状态加下一个字符唯一决定下一个状态。3.3 做题时如何避免概念混淆如果面试或者和别人讨论时被问到“KMP 属于动态规划吗”我的建议是这样回答按经典算法分类KMP 属于字符串匹配算法核心是前缀函数和失配回退思想不是动态规划它虽然用了“利用已经计算的中间结果避免重复匹配”这种记忆化思想但这种泛化的“动态规划思想”不等于算法分类上的动态规划。你也可以顺势补充一句如果非要把一切“用之前结果推导当前结果”都叫动态规划那几乎所有递推算法都能算 DP这种定义就失去区分度了。真正的动态规划要解决问题通常包含重叠子问题、最优子结构、无后效性三要素并且核心是“做决策、求最值或统计数”。KMP 更多是“按规则跳转匹配”不做最优决策。这么分析一遍KMP 这个热词不但没有白搜反而能帮你把动态规划的边界画得更清楚。很多人只背 DP 三要素从没试过用它去否定一个长得像 DP 的算法等到真正讨论问题时才发现概念是糊的。part06 阶段刷了这么多 DP 题正好拿 KMP 来检验你到底懂没懂 DP 的本质。4. 动态规划建模思维怎么练从“背模板”到“写状态”热搜词里出现了“动态规划建模思维”这个词听起来特别大但其实练起来非常落地。说白了建模思维就是看到一道题之后能准确回答四个问题状态是什么转移怎么来的边界怎么初始化遍历顺序是什么如果这四个问题你想都不想就打开题解那练再多也很难形成自己的建模能力。4.1 复盘法今天这题为什么没想到我练动态规划练到 day33 左右时给自己定了一个规矩每道题做完必须额外花十分钟写复盘笔记。笔记只记三样东西我最初的思路卡在哪里正确状态定义和我预想的有哪些差别这个题和之前哪道题的模型有相似性。别小看这个复盘动作。很多人的问题是“刷完就忘”白天高高兴兴 AC 一道题三天后重做依然一脸懵。原因就在于他根本没有把这道题压缩成“可迁移的模型”脑子里留下的只是零零碎碎的代码。比如 01 背包、分割等和子集、最后一块石头的重量 II这三道题表面完全不一样但本质都是“在数组里选一些元素让和尽量接近某个目标”。如果你复盘时发现了这层相似性后面再看新题就会觉得眼熟。建模能力就是在这一次次“找相似模型”的过程中长出来的。4.2 手写状态表三步法复盘还不够我强烈建议你在 part06 阶段至少亲手画三张二维 dp 状态表。别只在 IDE 里打印拿纸笔或者表格工具一步步自己填。以 01 背包为例物品体积 w [1, 2, 3]价值 v [15, 20, 30]背包容量 V 5。第一步画一个 4 行 6 列的表格行代表“只考虑前 i 件物品”列代表“容量 0 到 5”。第二步初始化第 0 行和第 0 列。第 0 行表示一件物品都没得选所有容量下的最大价值都是 0第 0 列表示容量为 0任何物品都放不下也都是 0。第三步按行填表。比如 i1 时物品 1 体积 1 价值 15容量 1 到 5 的格子都至少可以放下物品 1所以从容量 1 开始全部变成 15。i2 时就要考虑了容量为 2 的格子可以不放物品 2 保持 15也可以放物品 1 再加物品 2 获得 35取最大就是 35。把整个过程填完你不仅得到了正确结果还会发现每一个新格子都是“上一行的同列值”和“上一行左边某个值加当前物品价值”的比较。这时候再回头看那一堆模板你会觉得它们不过是这个填表过程的代码化表达罢了。4.3 面试和解题里的“讲 DP”表达框架有了建模思维你还得把它说清楚。很多人做题会做一开口就乱原因是脑子里没有一个固定的表达框架。我习惯用下面这个模板组织语言我定义 dp[i][j] 表示……。对于第 i 个元素我有两种选择第一种是不选对应状态 xxx第二种是选对应状态 yyy。取这两个状态中更优的那个作为 dp[i][j]。边界情况是……。最终答案是 dp[n][m]。光是这一个模板就能把动态规划题的讲解逻辑理顺。比如 01 背包我会说我定义 dp[i][j] 为只考虑前 i 件物品、背包容量为 j 时的最大总价值。对第 i 件物品我不选的话状态还是 dp[i-1][j]选的话需要从容量 j-w[i] 转移过来再加上价值 v[i]。两种情况取最大值就是 dp[i][j]。边界是容量为 0 或没有物品时价值为 0。最终答案是 dp[n][V]。这个模板看起来简单但它强迫你在开口之前先想清楚状态定义。而动态规划题最怕的就是“状态定义都没想清楚就急着算”。养成这个表达习惯对面试、笔试、甚至写技术文档都很有帮助。5. 常见问题与排查技巧实录part06 阶段踩坑特别密集我把这几年刷题和带新人过程中遇到的高频问题整理成一个速查表每一条都是真实翻过车的。5.1 动态规划高频翻车点速查表症状可能原因修复思路一维背包结果比预期大很多01 背包的内层循环写成正序导致同一件物品被重复选取改成倒序遍历让 dp[j-w[i]] 还停留在上一轮状态完全背包结果偏小或者不对外层循环和内容容量循环顺序选错组合数被当成排列数或反过来根据“组合数外层物品内层容量、排列数外层容量内层物品”调整dp 初始全是 0答案一直是 0初始化方式不对。比如求“恰好装满”时没有把 dp[0] 设为 0、其他设为无穷大明确题目是“最多装”还是“恰好装满”对应不同初始值数组越界访问内层循环从 w[i] 开始但容量小于 w[i] 的物品没有处理加判断或者让循环变量直接决定边界防止下标小于 0递归写法超时自顶向下没有加记忆化或者记忆化数组维度不够使用 memo 数组递归前查表、递归后存表维度要对齐状态数量只会求最优值不会输出方案滚动数组覆盖了历史决策丢失路径换成二维 dp或用额外数组记录每个格子的转移来源最后回溯看不懂题目该不该用 DP没有对状态空间建模直接套模板先想清楚求什么再想是否存在重叠子问题和决策过程这张表你可以存在笔记里。part06 之后的动态规划题目变种非常多但底层的错误基本都能归到这几种原因。遇到问题先别急着改代码对照表格看一眼很多时候一眼就能定位。5.2 个人 Debug 三板斧实测如果你发现自己写的 DP 代码输出和预期对不上建议按下面三步来排查省时省力。第一板斧是打印状态表。在循环里把每次更新后的 dp 数组打出来观察它每一步是否符合预期。比如发现某一行的值莫名其妙比上一行还大很多大概率是遍历顺序导致同物品被多算。这个方法能让你把抽象的动态规划过程变成肉眼可见的表格。第二板斧是手推一个小样本。千万别拿大样例调试自己选一个只有三个物品、容量只有五的手工例子把期望的状态表先在纸上推出来再和代码输出逐一对比。对比过程中你会迅速定位到是哪一行第一个出错再反过来分析当前转移到底从哪里引入了错误。第三板斧是从暴力递归改成记忆化搜索。很多人一开始就写递推思维负担很大。遇到没把握的题时先写一个纯递归的暴力版本验证逻辑再在递归里加 memo 数组把它改成记忆化搜索最后再按记忆化搜索的推导改成递推。这种三步转换虽然慢但能大幅降低出错率尤其适合 part06 刚开始接触多状态转移时使用。5.3 认真回答“01背包属于动态规划吗”这种送分题除了 KMP 那个概念题热搜词里还有“01背包问题动态规划”。和 KMP 不同这个问题没什么争议01 背包是组合优化领域的经典离散问题解决它的主流精确算法就是动态规划。很多教材甚至直接把 01 背包作为动态规划入门的标准案例因为它包含了一个完整的 DP 要素链阶段物品、状态容量、决策选或不选、策略最优价值。但值得多说一句的是01 背包也可以用搜索、分支定界、甚至贪心近似来对付只是这些算法要么只适合小规模要么只能给近似解。动态规划之所以成为首选是因为它在多项式时间 O(n*V) 内解决了一个看似指数级的组合问题。理解这一点对你日后做算法选型很有帮助别只看“代码能跑”更要明白“为什么这种解法合适”。KMP 不属于 DP 的讨论也一样它教给我们的不是记忆一个结论而是学会用算法本质去分类。一个算法是不是动态规划看它是否具备重叠子问题、最优子结构、无后效性而不是看代码里有没有递归或数组。说到底part06 这个阶段真正宝贵的收获不是又背了几个背包模板而是你开始具备“从问题到模型”的抽象能力。我自己当时做完一遍状态表手推之后最大的变化是拿到一道偏难的动态规划题我不再条件反射地找题解而是会先跟自己说“这个状态可以怎么定义它和前几天的背包模型有没有关系”所以如果你现在正好也刷到 day33 动态规划 part06我的建议很朴素别急着往后赶进度回头把 01 背包的二维表亲手填一遍把完全背包的遍历顺序用两行代码对比一下再把“状态定义、转移方程、初始化、遍历顺序”这四个问题当成每道题的必答项目。坚持几天后你会发现动态规划不再是玄学而是一种你看得见、推得动、说得清的建模过程。后面还有 part07、part08但你已经不是在跟风刷题而是在建立属于自己的思维框架了。
阅读完成 · 觉得有帮助？
)
