很多初学者看到“动态规划”四个字就头大脑子里全是“状态转移方程”“最优子结构”“重叠子问题”这些概念堆砌越学越玄乎。但我刷了上百道 DP 题、也被面试官按在地上摩擦过几轮之后最大的感受是动态规划不是数学证明题它本质上是一套“怎么把暴力穷举变得高效”的思维工具。只要你掌握了拆解它的固定套路大部分 DP 题在你眼里都会变成同一道题。这篇文章我用自己的实战经验把动态规划的完整解题思路从头到尾捋一遍。包括怎么判断一道题能不能用 DP、怎么写状态定义和状态转移方程、常见的几种 DP 类型怎么识别、以及我踩过的那些坑。不说废话全是能直接拿去用的东西。1. 先把动态规划的底层逻辑掰开揉碎1.1 动态规划到底在解决什么问题一句话动态规划用来解决“决策问题”尤其是那种一步选完、后面还要接着选、而且前后选择会互相影响的问题。举一个特别生活化的例子你要从北京去上海可以坐高铁、飞机、或者自驾。每种方式花的钱和时间不一样。如果只考虑“怎么到上海最省钱”这是个单步决策比一比价格就行。但如果要考虑“中间还要在南京停一晚到了南京之后的交通方式会影响从南京到上海的开销”这就是多步决策问题你在北京做的选择会影响你后面能选什么、以及后面选什么的成本。动态规划就是专门处理这种“前面选完影响后面”的问题。从算法本质上讲动态规划是一种用空间换时间的暴力搜索优化。暴力穷举会把所有可能的决策路径都走一遍时间复杂度经常是指数级的动态规划则是把每个“状态”的结果记下来遇到相同的状态直接读答案避免重复计算。用一个经典例子说明斐波那契数列。朴素的递归写法def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这个写法没有错但它会把同一个子问题算很多遍。画出递归调用树就能看到fib(3)被fib(5)和fib(4)分别调了一次各自又往下递归了一遍。计算fib(40)就要重复计算无数次耗时指数增长。动态规划的做法是用一个数组把已经算过的结果存下来从fib(0)开始往fib(n)推def fib(n): dp [0] * (n 1) dp[0], dp[1] 0, 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]同样的问题后者把指数级优化成线性级。这就是动态规划的全部意义记住已经算过的东西不让程序做重复劳动。1.2 一个经典的不能再经典的入门例子我不太想直接给你甩一堆数学公式先用一个最入门、但已经把 DP 所有关键要素都包含了的例子来建立直觉爬楼梯。问题描述你正在爬楼梯每次可以爬 1 阶或 2 阶。问有多少种不同的方法可以爬到楼顶。第一次看到这个题的人都会想这不就是个排列组合问题吗但你仔细一想每次只能走 1 阶或 2 阶这意味着你到第i阶的方式只能是从第i-1阶走 1 步上来或者从第i-2阶走 2 步上来。也就是说到第i阶的总方法数 到第i-1阶的方法数 到第i-2阶的方法数。翻译成 DP 的语言状态定义dp[i]表示爬到第i阶有多少种方法。状态转移方程dp[i] dp[i-1] dp[i-2]。初始条件dp[0] 1站在地面上不动是一种方案dp[1] 1一步到第 1 阶。有没有发现这个问题的本质和斐波那契数列完全一样。一旦你建立了“状态”和“状态转移”这两个概念爬楼梯就只是一个披着应用题外衣的递推而已。1.3 动态规划五步法我的固定解题框架我在刷题过程中逐渐总结出一套自己的 DP 解题流程后来发现很多大佬的讲解也是这个思路。我称之为“动态规划五步法”确定状态定义dp[i]、dp[i][j]到底代表什么确定状态转移方程当前状态是怎么从前一个或前几个状态推导出来的确定初始化和边界条件最开始的那些状态值是什么确定遍历顺序是从前往后推还是从后往前推或者是二维遍历确定答案在哪里最终答案存在哪个状态里这个五步法看起来很朴素但如果你每次做题都严格按照这个流程来走而不是一上来就瞎猜状态转移方程你会发现 DP 题的正确率高很多。后面我会用一个完整的题目做全流程演示。2. 判定一道题能不能用动态规划2.1 动态规划的两大核心特征先说说怎么判断“这道题该用 DP”省得你把时间浪费在错误的方向上。动态规划能解决的问题必须同时具备两个特征第一个是最优子结构。问题的最优解包含了子问题的最优解。用大白话讲你只要知道前面几步的最优选择后面就可以在这个基础上做最优选择不需要关心前面到底是怎么走过来的。比如爬楼梯问题中到第 10 阶的方法数不管你是从第 8 阶还是第 9 阶跳上来的到了第 10 阶之后后续的走法只和第 10 阶本身有关和之前的具体路径无关。第二个是重叠子问题。不同的决策路径会走到相同的子状态。如果没有重叠子问题动态规划的空间换时间就无从谈起那就是纯递归或者分治的领域。比如归并排序子问题不重叠所以用分治而不是用 DP。这两个特征缺一不可。光有最优子结构没有重叠子问题用 DP 就是杀鸡用牛刀光有重叠子问题没有最优子结构比如求两点之间的最短路必须全局统筹DP 也搞不定。2.2 这些题型直接让你想到 DP实战中我会根据题目的特征快速判断方向。下面这些特征出现任何一个都可以优先考虑 DP求最值题目问“最大”“最小”“最多”“最少”等。比如最长递增子序列、最小编辑距离、最大子数组和。求方案数题目问“有多少种方法”“有多少条路径”。比如爬楼梯、不同路径问题、括号生成。求可行性问题问“能不能达到”“是否存在”。比如背包问题中判断是否能凑出某个总重量。有明确的“状态转移”关系当前步骤的决策依赖于前面的状态。比如股票买卖问题第i天的状态就是由第i-1天的状态推过来的。这些特征对应着 DP 最常见的几类子问题计数型统计方案数、最值型求极值、存在型判断可行性、复合型多个维度综合。2.3 什么时候不该用 DP这比什么时候该用 DP 还重要。我有段时间为了练 DP看到什么题都想往 DP 上套结果经常把自己绕进去。下面这几种情况不要用 DP问题没有后效性。所谓后效性就是当前状态会影响后面状态的决策。反过来如果前面的选择完全不影响后面的选择那就是独立的单步决策用贪心或者排序就能解决。比如“每次取数组中最大的数”你用 DP 就是想不开。没有重叠子问题。比如求二叉树的深度虽然可以定义dp[node] 1 max(dp[left], dp[right])但它本质上是自底向上的递归不会出现同一个子树算两遍的情况直接用递归更自然。状态空间爆炸且无法压缩。如果状态定义需要五六个维度而且每个维度取值范围都很大那 DP 的时间和空间复杂度可能直接上天这时候要考虑用其他算法或者改变问题建模方式。判断的核心不在于问题的形式而在于是否存在重复计算的子问题以及是否能通过状态来刻画决策过程。3. 状态定义与状态转移DP 的核心战场3.1 状态定义怎么想从暴力递归中找灵感我见过太多人卡在状态定义这一步。给你一个诀窍状态定义往往可以暴力递归的参数中找到。假设你面对一个新题你不知道 DP 怎么做你总该知道暴力怎么吧。暴力递归时每次递归需要传入哪些参数这些参数的值就是状态的维度。举个例子求字符串s的最长回文子序列长度。暴力递归时你自然会想到用一个区间[i, j]来表示当前考虑的子串范围那么状态就是dp[i][j]表示s[i..j]的最长回文子序列长度。这种从暴力参数映射到状态维度的做法能解决 80% 的状态定义问题。剩下的 20% 需要你根据题目中的“变量关系”自己提炼维度。3.2 状态转移方程怎么写两个核心思路有了状态定义转移方程就顺理成章了。我总结出两个最常用的思考角度角度一最后一步发生了什么。这是最常用、也是最好用的思路。想一想达到当前状态最后一步是怎么来的把所有可能的情况列出来然后取最值或者求和。比如“最少硬币凑出amount”这个题最后一步一定是某种面额的硬币所以dp[amount] min(dp[amount-coin] 1)对每种面额的硬币取最小。角度二划分成互不重叠的子问题。把当前问题分割成几个更小的问题每个小问题单独求解然后合并。这个思路尤其适合区间 DP。比如戳气球问题固定一个最后被戳破的气球把区间分成左右两个子区间各自独立求解。这两个角度听起来都很简单但真正难的是“怎么想到以这样的最后一步作为划分依据”。这需要大量刷题积累但如果你每一步都强迫自己回答“最后一步干了什么”思路自然就打开了。3.3 初始化与边界最容易翻车的环节我敢打包票大部分 DP 题你写出来的第一版代码错的地方都是初始化和边界条件。这也是初学者和高手差距最明显的环节之一。初始化要看状态定义的含义。dp[0]代表什么dp[i][0]呢它们是不是应该在循环开始前就设定一个特定的值边界条件则要重点关注数组越界的情况。比如dp[i] dp[i-1] dp[i-2]如果i从 0 开始循环i-1和i-2就会访问负数下标。解决方案要么把 dp 数组开大一点把下标平移一位要么在循环里加判断要么单独处理边界情况。还有一类经典边界在处理字符串 DP 时通常要人为增加一个dp[i][0]或dp[0][j]的空串边界值。比如编辑距离问题dp[i][0] i表示从一个长度为i的字符串变成一个空字符串需要删除i次这个初始化是整个人转移方程的基石。3.4 一个五步法完整演示最长递增子序列光说不练假把式我们用 LeetCode 300 题“最长递增子序列”完完整整走一遍五步法。题目给定一个整数数组nums找到其中最长严格递增子序列的长度。子序列可以不连续。第一步定义状态。dp[i]表示以nums[i]结尾的最长递增子序列的长度。注意这个定义的关键点“以nums[i]结尾”。这个约束条件很重要它保证了状态转移的可行性。如果不加这个约束就没办法描述“后面元素接了前面的哪个尾巴”。第二步状态转移方程。dp[i]怎么来想一下最后一个元素nums[i]它一定接在某个比它小的元素nums[j]后面其中j i。那么以nums[j]结尾的最长递增子序列长度加上nums[i]自己就是以nums[i]结尾的最长递增子序列长度。所以对每个i遍历所有j i如果nums[j] nums[i]就尝试更新dp[i] max(dp[i], dp[j] 1)。第三步初始化。每个元素至少可以单独成为一个长度为 1 的递增子序列所以dp[i] 1。第四步遍历顺序。从左到右遍历i内层遍历所有j i。第五步答案。答案不是dp[n-1]而是所有dp[i]中的最大值。因为最长递增子序列可能以任意一个位置结尾。代码实现def lengthOfLIS(nums): if not nums: return 0 n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)就这么简单的几行代码包含了 DP 的全部精髓。你要是能独立推导出这个解法说明你已经入了 DP 的门。4. 动态规划的四大经典模型识别套路4.1 线性 DP最简单也最常用线性 DP 是最基础的一类。状态定义通常是一维的dp[i]只依赖前面几个状态。典型问题包括爬楼梯、最大子数组和、最长递增子序列LIS、打家劫舍等等。这类题的核心特征是问题可以沿着一条“线”往后推。可能是数组下标、可能是天数、可能是序列长度。以打家劫舍为例你是一个小偷不能偷相邻的两家。dp[i]表示偷到第i家时能获得的最大金额。两种选择偷第i家则前一家不能偷最大收益是dp[i-2] nums[i]不偷第i家最大收益是dp[i-1]。所以dp[i] max(dp[i-1], dp[i-2] nums[i])。做线性 DP 的套路就是先把线找出来再想清楚当前这个位置“选”和“不选”对应什么状态。4.2 区间 DP从小区间扩到大区间区间 DP 的状态定义通常是二维的dp[i][j]表示从下标i到j这个区间内的最优解。这类问题的核心是大区间的最优解由小区间的最优解合并而来。典型问题最长回文子序列、戳气球、石子合并。以石子合并为例一排石子堆每次可以合并相邻两堆代价为两堆石子数之和问把所有石子合并成一堆的最小总代价。dp[i][j]表示合并第i堆到第j堆的最小代价。关键在于枚举分割点k把[i, j]分成[i, k]和[k1, j]两段分别合并最后再把两堆合并起来。区间 DP 的遍历顺序很讲究不能简单地按i从小到大、j从大到小乱来通常要按区间长度从小到大枚举。for length in range(2, n 1): # 区间长度 for i in range(0, n - length 1): # 区间起点 j i length - 1 # 区间终点 dp[i][j] INF for k in range(i, j): # 分割点 dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost(i, j))这个按长度遍历的顺序保证了计算dp[i][j]时所有更短的子区间都已经被计算过了。4.3 背包 DP经典中的战斗机背包问题是 DP 的一个重要分支也是面试常客。最经典的是 0-1 背包有N件物品和一个容量为V的背包每件物品只能选一次求能装入背包的最大价值。状态定义dp[i][j]表示前i件物品放入容量为j的背包能获得的最大价值。对第i件物品要么不选要么选。于是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这里有个空间优化的心法一维数组滚动dp[j]表示容量为j时的最大价值。但要注意0-1 背包必须倒序遍历容量否则同一件物品会被重复放入这也是区分 0-1 背包和完全背包的关键。for i in range(n): for j in range(V, w[i]-1, -1): dp[j] max(dp[j], dp[j-w[i]] v[i])如果j正序遍历dp[j-w[i]]可能已经是放入了当前物品的状态就会导致物品被无限次使用——那正好是完全背包的写法。这个细节是背包问题的灵魂所在一定要刻在脑子里。4.4 状态压缩 DP把多维压成一维状态压缩 DP 通常用于处理那些“是否选取”型问题常见于旅行商问题TSP、集合划分问题等。核心思想是把一个集合的选取状态编码成一个整数用整数的二进制位表示每个元素是否被选中。比如有n个城市dp[mask][i]表示已经访问过的城市集合为maskmask的二进制第k位为 1 表示访问过第k个城市当前在第i个城市时的最短路径长度。转移就是枚举下一个没访问过的城市。状态压缩 DP 的状态数量为O(2^n * n)。n一般不超过 20否则状态数量会爆炸。能压的维度就压不能压的维度老老实实开多维数组。4.5 一个表帮你快速定位 DP 类型问题特征DP 类型典型状态定义经典例题单序列、单数组、线性顺序线性 DPdp[i]打家劫舍、最大子数组和字符串/区间上的操作区间 DPdp[i][j]最长回文子序列、编辑距离有重量/容量/数量的选择问题背包 DPdp[i][j]i 为物品j 为容量0-1 背包、完全背包集合选取、排列组合式状态压缩 DPdp[mask][i]旅行商问题、状态压缩 DP多阶段决策过程多阶段 DP按阶段拆分的多维数组股票买卖、买卖最佳时机这张表不是绝对的但当你做题没头绪时对着表格找相似题能省不少时间。5. DP 与递归/贪心/暴力的分界线5.1 动态规划和递归、分治的区别动态规划和递归本质上都依赖“子问题分解”但 DP 强调“重叠子问题”的复用而递归/分治默认子问题相互独立。如果递归调用树中存在大量重复计算加一个缓存记忆化搜索就变成了 DP。所以记忆化搜索本质上是“自顶向下的 DP”而通常说的 DP 是“自底向上的递推”。两者各有优劣自顶向下记忆化搜索写起来直观顺着题目的自然思考方式递归不容易出错。自底向上递推没有递归栈开销性能更好但需要先搞清楚所有状态的依赖顺序。我的习惯是如果状态转移方程想不清楚先写一版带缓存的递归确认思路对不对再改写成递推。这个习惯让我少踩了很多坑。5.2 动态规划和贪心的最大不同贪心是每一步都做当前看起来最好的选择期望局部最优等于全局最优。但贪心只适用于有贪心选择性质的特定问题。用经典的“零钱兑换”问题对比有面额[1, 3, 4]的硬币要凑 6 块钱。贪心会先选 4、再选 1、再选 1用了 3 枚。但最优解是 33只用 2 枚。贪心错了吗不是错是不适用。而 DP 会穷举所有组合自然能找到最优解。判定的关键还是那两条有没有最优子结构、有没有重叠子问题。有重叠子问题DP 就有优势没有重叠子问题贪心往往更快。5.3 DP 为什么比暴力高效状态数的艺术暴力穷举的时间复杂度通常是所有路径的总数动态规划的时间复杂度是状态总数乘以每个状态的转移代价。以爬楼梯为例暴力fib(40)大约要算 3 亿次DP 的状态总数是n1每个状态转移O(1)所以复杂度是O(n)。差别是天壤之别。再以矩阵路径问题为例从矩阵左上角走到右下角暴力枚举所有路径是指数级但 DP 状态只有O(m*n)个。这就是“状态数”这个概念在 DP 分析中的作用一旦状态数可控DP 的时间复杂度就可控。5.4 一个实战中的选择口诀在我自己的刷题决策里我常用这样一个判断顺序题目问最优解或方案数优先考虑 DP 或贪心。当前选择会影响后续状态大概率是 DP不是贪心。递归中有没有重复子问题有则加缓存本质就是 DP。问题规模很大但状态维度有限DP 是首选方向。这套判断不是绝对真理但它能让你在考场上或季度绩效评审的算法题环节快速找到方向。6. 动态规划的空间优化套路6.1 滚动数组把二维压成一维或两行很多 DP 的状态转移只依赖前一行或前两行的数据。这种情况下没必要保留整个二维数组用滚动数组可以把空间复杂度从O(n^2)降到O(n)。最经典的例子就是爬楼梯dp[i]只依赖dp[i-1]和dp[i-2]所以只需要两个变量滚动更新a, b 1, 1 for i in range(2, n 1): a, b b, a b print(b)再比如矩阵路径问题dp[i][j]只依赖dp[i-1][j]和dp[i][j-1]可以只用一维数组配合逐行更新的方式实现同样的效果。滚动数组的原理就是“只保留当前计算需要的前几行数据”在空间受限的比赛中非常实用。6.2 状态压缩的边界什么时候不能压缩空间优化不是万能的。如果你的状态转移方程依赖的是跨两行以上的数据或者是二维矩阵中斜方向的数据那么滚动数组可能就不太适用。比如编辑距离问题dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]虽然也能优化成一行加几个变量但实现复杂度会明显上升这时候就要权衡是保空间还是保代码可读性。我的原则是面试和工作中优先保证正确性和可读性空间优化是加分项不是必须项。只有在明确讨论空间复杂度、或者数据规模确实逼着你省内存的时候才值得花心思去做空间优化。6.3 从二维到一维的通用写法套路以 0-1 背包为例完整展开一下从二维到一维的推导过程。原始二维代码是这样的dp [[0] * (V 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, V 1): if j w[i-1]: dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i-1]] v[i-1]) else: dp[i][j] dp[i-1][j]观察发现第i行只依赖第i-1行于是只用一维数组dp[j]表示容量为j时的最大价值dp [0] * (V 1) for i in range(n): for j in range(V, w[i]-1, -1): dp[j] max(dp[j], dp[j-w[i]] v[i])这里的核心就是内层倒序遍历。倒序保证了dp[j-w[i]]是“没有放过当前物品”的旧值。如果你写成正序dp[j-w[i]]可能已经在这一轮被更新过就变成了完全背包。这个细节我在面试讲解时反复会提到因为它是理解背包 DP 空间优化最关键的钥匙。7. 从零开始刷 DP 的实战路线7.1 第一阶段建立“状态”直觉刚接触 DP 时不要直奔难题。先从最经典的几道入门题开始目标是建立“状态”这个核心概念爬楼梯斐波那契数列最大子数组和打家劫舍不同路径这几道题看完答案后一定要自己手写一遍并且用五步法都写一遍。不要背代码要能独立给出状态定义和转移方程。这一阶段我建议 2~3 天搞定。7.2 第二阶段掌握线性 DP 和背包 DP接下来可以进入更常见的线性 DP 题最长递增子序列LIS最长公共子序列LCS编辑距离零钱兑换0-1 背包变形分割等和子集背包 DP 建议集中刷因为它的状态定义套路非常固定一旦你彻底理解“容量”和“物品”两个维度所有背包问题0-1 背包、完全背包、多重背包都是同一套逻辑的变体。这个阶段的关键收获见到一道题能判断它属于“选或不选”型、“按顺序选”型、还是“区间合并”型。7.3 第三阶段战胜区间 DP 和状态压缩 DP这个阶段可以挑战最长回文子序列石子合并戳气球旅行商问题状态压缩区间 DP 的遍历顺序是个难点我建议反复写石子合并把这个“按长度从小到大枚举”的代码模板刻进肌肉记忆。状态压缩 DP 我先把mask的二进制思想想明白再动手写代码。这个阶段不追求速度追求的是每道题都能从头推导出状态定义和转移方程。7.4 刷题数量的迷思很多人问“ DP 至少要刷多少题才能有感觉”我的回答是质量比数量重要得多。50 道经典 DP 题每一道都独立推导、复盘、总结效果远超盲目刷 300 道。我自己有一个记录表每道 DP 题都记录四件事状态定义是什么、转移方程是什么用文字描述不写代码、初始化和边界是什么、卡了多久。这个表复盘起来特别好用。7.5 面试中 DP 题的答题节奏面试遇到 DP 题千万别上来就闷头写代码。我建议按这个节奏来先讲清楚状态定义。哪怕不确定也要说出来让面试官纠正这个过程能帮你理清思路。再讲状态转移方程。用“最后一步是什么”来组织语言。然后说初始化和遍历顺序。最后写代码。这样即使最终代码有 bug面试官也能看到你思路是清晰的。比起直接写对他们更看重你的思维过程。8. 动态规划常见问题与避坑心得8.1 状态定义错误把维度漏了最常见的低级错误是状态定义缺维度。比如股票买卖问题如果你只用dp[i]表示第i天能赚到的最大利润就会漏掉“当前持有股票”和“当前不持有股票”两个子状态。正确做法是dp[i][0]表示第i天不持有股票的最大利润dp[i][1]表示第i天持有股票的最大利润。避坑指南状态定义之前先问自己三个问题这个状态能不能完整描述问题当前的情况这个状态会不会把不同的情况混在一起如果从状态 A 转移到状态 B有没有超出定义范围的跳跃8.2 数组越界最粗心也最常见的错误爬楼梯的dp[i] dp[i-1] dp[i-2]如果i从 0 开始直接就数组越界。编辑距离中dp[i-1][j-1]在i0或j0时也会越界。避坑指南写转移方程前先把初始化的值想清楚哪些下标是合法的。通常我们会把 dp 数组多开一位或者先给边界赋值保证循环体内不会出现非法下标。8.3 初始值含义混淆dp[0]是 0 还是 1这是一个能让人抓狂的问题。爬楼梯中dp[0] 1是因为“不动也是一种方法”但最长递增子序列中每个dp[i]至少为 1。如果你没有仔细想清楚每个状态定义的实际含义初始值很可能是错的。避坑指南每写完一个 DP在脑中用极小规模的例子手动跑一遍。比如n1、n2确认初始值推出来的结果是否符合直觉。8.4 转移顺序问题乱序遍历白算区间 DP 的遍历顺序尤其容易错。如果你按i从小到大、j从大到小遍历很可能会用到还没有算出来的状态。回到石子合并的例子计算dp[i][j]时需要dp[i][k]和dp[k1][j]这两个区间的长度都小于j-i1。所以必须按长度从小到大遍历才能保证依赖的子区间已经算完。避坑指南当你不确定遍历顺序时画出状态依赖图。每个状态指向它依赖的状态然后按照依赖图的拓扑顺序遍历。8.5 最小值和最大值的初始化差之毫厘谬以千里求最小值的问题dp数组通常初始化为float(inf)求最大值的问题初始化为-float(inf)或 0。如果初始值设错转移方程取min或max时会被初始值污染。比如零钱兑换问到“最少硬币数”dp[amount]初始化为inf如果最后依然是inf说明无法凑出该金额应该返回-1。8.6 常见问题和解决方案速查表问题现象可能原因解决方案答案一直偏小初始值设置成了 0但应该设为inf/-inf根据求 min 还是求 max 重新设置初始值数组越界循环边界没处理扩大 dp 数组、单独处理边界、循环加判断物品被重复选取0-1 背包内层正序遍历0-1 背包内层改倒序遍历区间 DP 输出错误遍历顺序不对改为按区间长度从小到大遍历状态转移漏了情况状态定义太粗增加维度区分不同子状态递归版超时没有加缓存改成记忆化搜索或自底向上 DP8.7 排查经验分享卡住超过 20 分钟我一般不会死磕直接看题解看完一定要求自己独立推导并重新写一遍。这个方法看起来简单但很多人做不到“看了之后合上答案自己重写”导致下次遇到还是不会。还有一个小技巧如果某个状态的转移方程非常复杂试着先用记忆化搜索写一版。递归版思路正确了再翻译成迭代版要容易得多。我自己至少有一半的 DP 题是先写递归验证再改成递推的。这个技巧也帮初学者建立信心感觉 DP 很难但递归总还会吧。在实际的刷题过程中把 DP 当作递归的“带缓存”版本来理解整个学习的陡峭程度会下降不少。9. 动态规划背后的思维模式升级9.1 从“找答案”到“定义状态”的思维转变这是 DP 思维和普通算法思维的最大差异。普通算法思维是“我要算出一个答案”比如排序、二分查找你直接对着目标操作。DP 思维是“我要把过程拆成一层一层的状态然后顺着状态往后推”答案只是最后一个状态的取值。举个真实例子我做过一个股票最大收益题。一开始我的想法是找峰谷差值最大的那一段写出来一堆判断条件代码又长又容易错。后来用 DP 把每天持有和不持有股票的状态写出来代码短了逻辑也清晰了。这就是“状态”思维和“找答案”思维的区别。9.2 DP 是很多高级算法思想的地基动态规划不是终点。学会了 DP你再去看 Floyd 最短路、区间调度、图像分割里的能量函数优化、自然语言处理里的维特比算法会发现它们的内核都是 DP。比如维特比算法用于 HMM 解码、词性标注它的核心就是一个 DP过程在状态序列上按时间步推进每个时间步保留到某个状态的最大概率路径。你可以把它理解成一个“带权重的路径 DP”。这些算法看着高深底层思想拆开了就是状态定义 转移方程两个组件。所以把 DP 学好不仅是为了应付面试题更是帮你在未来的技术阅读中具备更深的拆解能力。9.3 我在实际刷题中悟到的两个心法第一个心法先把问题变“小”。面对任何 DP 题先问自己如果只有一个元素、只有一个子串、只有一天时间答案是什么这个最小规模问题的答案很大程度上就是初始值。第二个心法把转移方程说人话。不要直接用数学符号写方程先用一句人话描述“当前状态的值 上一步选了某个选项的结果 这个选项带来的收益。”能说出这句话再翻译成代码就不难了。这两个心法听起来像鸡汤但真的帮我解决了很多道难题。算法思维和语文能力在 DP 这里意外地交汇了——能把逻辑讲清楚的人写出来的 DP 代码通常也干净。9.4 从固定套路走向灵活变通等你刷了一定数量后会发现 DP 的难点已经不在“怎么套模板”而在“怎么根据问题语义设计合适的状态”。有的题状态是二维的有的题状态是三维的有的题需要把状态设计成布尔值有的题需要设计成字典。这个时候你已经不会拘泥于“线性 DP”还是“背包 DP”的分类了而是在理解问题本质后自然选择合适的工具。这个阶段我特别建议去做几道“不那么模板”的 DP 题比如“最大矩形面积”“自由之路”“超级洗衣机”这种打破你对 DP 的固定印象。经历过这个阶段以后你才真正能把 DP 变成自己的解题能力而不是背下来的套路。我个人在实际操作中的体会是动态规划其实不是一堆公式的堆砌它更像是一套“把复杂问题拆成递归重复结构”的思维方式。你需要的不是天赋而是找到正确的方法论然后用足够的练习把它内化成直觉。如果你读完这篇文章能闭上眼把“状态定义、转移方程、初始化、遍历顺序、答案位置”这五个步骤复述出来再亲手做三道经典题你就已经比大多数只会背模板的人强了。最后再分享一个小技巧刷 DP 题的过程中准备一个错题本不用抄题目只记一句话——比如“这题我忽略了 dp[i][j] 依赖 dp[i-1][j-1] 需要单独初始化”。到了复盘的阶段你会感谢这个习惯的。