坚持到 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 轮的数据，没必要把之前所有轮次都留在内存里。
一维模板长这样：
vector<int> 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 背包唯一的模型区别是：每件物品可以无限次取用。代码上的变化更是小到令人发指——内层循环从倒序改成顺序即可：
vector<int> 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 数组），它的计算过程长这样：
vector<int> prefixFunction(string s) { int n = s.size(); vector<int> 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。
第三步，按行填表。比如 i=1 时，物品 1 体积 1 价值 15，容量 1 到 5 的格子都至少可以放下物品 1，所以从容量 1 开始全部变成 15。i=2 时就要考虑了：容量为 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，但你已经不是在跟风刷题，而是在建立属于自己的思维框架了。
