动态规划这个算法在技术圈里被讨论的频率一直很高。不管是刷题准备面试还是做工程里的路径规划、资源调度、能耗优化都会碰到它。但很多朋友对它又爱又恨看别人的题解觉得“就这挺简单的”真到自己上手写却总卡在状态定义那一步或者被优化的各种技巧绕晕。这篇文章我不打算像教科书那样把动态规划从头到尾平铺直叙一遍。我的思路是先说清楚动态规划究竟在解决什么本质问题再把三大基本要素逐个拆开揉碎给你一套拿到题就能照着走的解题步骤最后用几个有代表性的例题把从基础版本到优化版本的全过程完整走一遍。你会看到同一个问题是怎么从 O(2^n) 的暴力递归一步步进化到 O(n) 的动态规划甚至空间复杂度还能压到 O(1)。文章适合这几类人看正在准备算法面试的开发者、刚接触动态规划但被各种概念绕晕的学生、以及在实际工程项目中需要用动态规划思想做资源分配或路径优化的人。我会尽量用大白话解释每个“为什么”而不是只告诉你“是什么”。1. 动态规划到底在解决什么问题很多教材一上来就给出动态规划的定义说它是“把原问题分解成若干子问题求解”的方法。这话没错但不够解渴。它没有回答一个关键问题为什么有些问题分解成子问题之后就能高效求解有些却不行1.1 从暴力递归到记忆化搜索的进化逻辑我们先看一个最经典的问题——斐波那契数列。学过递归的朋友都知道用递归求第 n 项是这样的def fib(n): if n 1: return n return fib(n-1) fib(n-2)代码非常简洁但性能极其糟糕。算 fib(40) 就已经明显卡顿算 fib(50) 直接等到怀疑人生。原因在于这个递归过程里发生了大量的重复计算fib(5) 会重复计算 fib(3) 两次、fib(2) 三次、fib(1) 五次。这就像你在一家餐厅当传菜员客人点了十桌同样的菜你每送一桌都跑去后厨重新做一遍。明明后厨已经做好过一次放在出菜口就能直接端走为什么还要反复折腾动态规划的第一层进化就是记忆化搜索——既然子问题会重复出现那我把已经算过的结果存下来下次直接用。这对应一个后厨“出菜口”的角色术语叫 memo 数组def fib_memo(n, memo{}): if n 1: return n if n not in memo: memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n]加了 memo 之后每个 n 只被真正计算一次。时间复杂度从 O(2^n) 降到了 O(n)这差距有多大呢n50 时前者要做几十万亿次加法后者只需要做 50 次。1.2 从记忆化搜索到底层状态的推进顺序记忆化搜索的特点是“自顶向下”从大问题出发需要谁就递归调用谁。这个思路很直观但有两个问题一是递归本身有函数调用开销。深度很大的时候可能爆栈比如 n10 万普通递归根本跑不动。二是它没有揭示动态规划的本质。动态规划真正的精髓在于状态转移——从小到大用已经算出来的小状态去推导大状态形成一个流水线式的推进过程def fib_dp(n): dp [0] * (n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这里 dp[i] 就代表“斐波那契数列的第 i 项”这个子问题的答案。for 循环里那句dp[i] dp[i-1] dp[i-2]就是递推公式也就是动态规划里说的状态转移方程。你可能会问记忆化搜索和递推版本本质上都是避免重复计算那为什么递推版本更受青睐因为递推版本把“子问题之间的依赖关系”显式地表达成了一个有向无环图。从 dp[0] 一路推到 dp[n]不存在递归的栈溢出风险也不存在重复计算的开销。更重要的是当你面对复杂问题的时候递推版本更容易让你看清问题的结构——每个状态是怎么来的、依赖哪些前置状态一目了然。1.3 动态规划和分治、贪心的核心差异很多初学者分不清动态规划、分治和贪心三者的区别。我拿生活中常见的场景类比一下。分治是把一个大任务拆成几个独立的小任务分别完成最后汇总。比如你要打扫一栋三层楼的房子三个人各负责一层。这里的关键是各层之间互不影响。典型的代表是归并排序。贪心是每一步都做当前看起来最好的选择并且不回头。比如你要从一堆面额的人民币里凑出 200 块钱你会下意识地先拿最大的面额。贪心算法快但它的前提是“局部最优能达到全局最优”这个前提在很多时候并不成立。动态规划则更像是在多条路径中做决策并且每条决策之间是有重叠和依赖的。你从 A 地开车去 B 地路上有很多岔路口每个路口的选择会影响后续路径。动态规划会帮你把每个交叉路口到终点的最短距离都算出来然后每到一个路口只需要查一下“从这里到终点怎么走最短”再结合当前这段路的距离就能做出最优决策。所以三者的核心区别我总结成一张表算法子问题特点决策方式典型问题分治子问题相互独立先分解后合并归并排序贪心只做一次决策不回头局部最优推进部分背包问题动态规划子问题重叠且有依赖记录历史上所有最优子解0-1背包、最短路径判断一个问题适不适合用动态规划关键就看两条有没有重叠子问题、有没有最优子结构。这两个概念在下一节重点展开。2. 三大基本要素的拆解与理解动态规划的三个基本要素是状态定义、状态转移方程、边界条件。这个说法在很多书里都能看到但大家真正卡住的恰恰是这三件事中的第一件——状态不会定义。2.1 状态定义一切问题的起点状态定义是什么简单说就是你要用什么样的“位置变量”来描述一个子问题的答案。以跳楼梯为例你每次可以爬 1 级或 2 级台阶爬到第 n 级有多少种不同的爬法如果定义dp[i]为“爬到第 i 级台阶的爬法总数”这就是一种状态定义。有了这个定义自然而然就能想到要到达第 i 级最后一步要么是从第 i-1 级爬 1 级上来要么是从第 i-2 级爬 2 级上来。所以dp[i] dp[i-1] dp[i-2]这看起来很简单但换个场景你可能就不太会定义状态了。比如最长递增子序列LIS问题dp[i]如果不定义为“以第 i 个元素结尾的最长递增子序列长度”而定义为“前 i 个元素中的最长递增子序列长度”那状态转移就会变得极其别扭。区别在哪里因为“以第 i 个元素结尾”这个定义让你能直接知道上一状态和当前状态之间的关系——你只需要去前面找比 nums[i] 小的元素 jdp[i] 就能通过 dp[j] 推导出来。而“前 i 个元素的最长递增子序列”这个定义丢掉了最后一个元素是谁的信息导致你无法确定新来的元素能否接在后面。所以状态定义有一条核心经验状态里要包含足够的信息来描述当前子问题的“边界情况”让转移过程合理不丢信息。2.2 状态转移方程把问题变成数学公式状态转移方程描述的是当前状态怎么通过之前的状态推导出来。它本质上是问题结构的一种数学刻画。写转移方程的时候我习惯问自己三个问题当前这个状态可以由哪些前驱状态到达到达当前状态的“代价”或“动作”是什么如果有多个来源要怎么取舍取 min、max、相加、计数等比如打家劫舍问题你是一个小偷沿街有一排房子每个房子里有不同金额的现金你不能偷相邻的两家问最多能偷多少。先定义dp[i]为偷到第 i 间房子时能获得的最大金额。然后考虑第 i 间房子偷不偷如果偷第 i 间那第 i-1 间就不能偷最大收益是dp[i-2] nums[i]如果不偷第 i 间那最大收益就是dp[i-1]所以转移方程为dp[i] max(dp[i-1], dp[i-2] nums[i])从这个例子你可以看出写转移方程的功夫全在“分析清楚每一种可能的情形并计算出对应的值最后做决策”。这里收获的一个经验是写方程之前先想思路而不是先想代码。先用自然语言把“从上一个状态到这一个状态发生了什么”说清楚再说成数学表达式。很多题解直接扔出转移方程初学者看不懂就是因为少掉了那个“用大白话描述决策过程”的中间步骤。2.3 边界条件与初始化最容易被忽视的坑边界条件通俗讲就是递推链条的起点在哪里。还是拿打家劫舍举例。当 i 0 时只有一间房那dp[0] nums[0]。当 i 1 时有两间房但不能同时偷所以dp[1] max(nums[0], nums[1])。这两个基础值不初始化递推就无法进行。很多题目表面看起来状态定义出来了转移方程也写出来了但一跑就错问题就出在边界上。我总结了边界条件的三个检查维度第一初始值是否符合逻辑定义。比如dp[0]表示“没有房子可偷时”的收益那应该初始化为 0。有些题会要求下标从 1 开始有些从 0 开始这直接决定了 dp 数组的长度和初始化的位置。第二遍历顺序是否正确。必须保证计算当前状态时它依赖的状态已经被计算过了。常见的遍历顺序有从头到尾一维顺序往后推、从左上到右下二维网格、反着遍历背包问题的滚动数组优化时特别容易出现这个问题。第三特殊边界有没有防御。比如数组长度只有 1 的时候循环根本进不去你直接 return nums[0] 才是对的。所以写代码前一定要想清楚输入为空、输入长度为 1、极端值比如全是负数时程序会不会出问题。网上很多人在讨论动态规划时最爱问“为什么我的代码总是差一个数”。绝大多数情况就是边界条件没处理好——要么 dp[0] 没想清楚该等于多少要么 for 循环的起止范围差了一个位置。2.4 判断一个题能不能用动态规划前面提到两个判断标准重叠子问题和最优子结构。我把这两个概念再讲透一点。重叠子问题怎么理解你画一下递归调用树如果同样的子问题节点反复出现那就存在重叠子问题。典型的反面例子是归并排序它切割出来的子数组互不重叠所以不需要 memo。最优子结构怎么理解原问题的最优解可以由子问题的最优解直接组合出来。举个例子你要规划一条从杭州到上海的最短路径如果必经苏州那么杭州到苏州这段路也必须是杭州到苏州的最短路径。如果不满足这个性质比如“子路径最短”会导致后续路段更长最终整体反而更差类似那种带油耗衰减或时间窗口限制的问题那动态规划就直接没法用得另想别的办法。还有一层微妙的东西需要区分。动态规划和贪心的判断容易混淆。贪心问题也要求最优子结构但贪心只保留一个候选解往前走动态规划则是把每个位置的最优子解都保存下来供后续使用。换句话说动态规划是“全都要”贪心是“只要一个”。这也是为什么动态规划要开一个数组记录历史而贪心只需要几个变量。3. 一套实战性很强的五步解题法这部分我分享一套自己一直在用的解题流程。很多朋友拿到一道动态规划题第一反应是“这题我好像见过但想不起来怎么做”或者“看一眼答案瞬间懂了合上书又不会了”。这两种情况都是因为没有形成固定的分析框架。我总结的五步法核心思路是把一个模糊的“不会做”拆成五个具体的“检查项”每一步都有明确产出物。这五个步骤是3.1 第一步穷举分析找出子问题的递推结构在写任何代码之前先用最笨的方法把小规模输入的结果手推出来。比如 n0、1、2、3、4 这种情况各是多少写在纸上观察规律。关键是不仅要看答案还要看答案之间是怎么“长出来”的。比如跳楼梯问题爬到第 1 级有 1 种爬到第 2 级有 2 种爬到第 3 级有 3 种……你会发现 dp[3] dp[2] dp[1]由此暴露出转移结构。我特别喜欢这个步骤因为它能把抽象的“为什么是这个转移方程”具象化。当你亲手推出前几项之后心里对题目就有了底。3.2 第二步定义状态明确每个 dp[i] 的含义这个前面详细讲过了这里只说一个实战技巧状态定义不要怕各种维度多就怕维度少导致信息不足。新手经常会为了“省空间”把二维压成一维结果把逻辑绕晕了得不偿失。定义状态的时候先不管空间复杂度怎么清晰怎么来。先把正确版本写出来再谈优化。先追求“能解出来”再追求“解得好”。这句话送给所有刚开始学动态规划的朋友——不要第一步就想走捷径。3.3 第三步推导状态转移方程这部分我建议用表格来辅助思考。以二维动态规划比如编辑距离为例画一个表格横坐标是第一个序列的处理进度纵坐标是第二个序列的处理进度然后看当前位置的值能由哪些格子推导出来。推导转移方程时注意两点一是覆盖所有可能的情况。拿编辑距离来说当前位置的字符可能相等也可能不等这两种情况要分别讨论不能漏。二是决策的可逆性。也就是说你列举的前驱状态应该能对应到一种真实存在的“操作”反过来你从任何一个前驱状态也能合法地走到当前状态。很多同学转移方程写错就是因为念叨的前驱关系不对应实际操作。3.4 第四步确定初始化和遍历顺序状态转移方程只是骨架初始化和遍历顺序才是让代码真正跑起来的血肉。我在这给一个通用模板# 1. 创建 dp 数组 # dp 数组的大小 状态需要的维度 1如果要用到 dp[-1] 或 dp[0] 作为边界 # 2. 初始化基础状态 # 3. 遍历所有状态 # 遍历时的顺序要保证计算 dp[i] 时dp[i] 依赖的所有状态都已经被计算过 # 4. 返回目标状态遍历顺序的细节经常出问题的地方是背包问题。背包问题的滚动数组优化需要倒序遍历容量很多人不理解为什么就在那硬背。等后面讲到例题的时候我会专门解释这个“为什么”。3.5 第五步复杂度检查与空间优化最后一步才去考虑优化。优化的顺序也有讲究先看时间能不能优化换更优的算法思路再看空间能不能优化滚动数组、状态压缩。时间优化的手段通常有剪枝去掉一些确定不可能的状态。例如某些状态下剩余容量不够了直接跳过。换状态定义把高维状态压成低维或者把指数级状态压缩成多项式级。这是质的提升。数据结构加速比如最长递增子序列的 O(nlogn) 解法就用了 vector 加二分查找这种优化能显著提升性能。空间优化的手段则相对固定滚动数组因为有些状态转移只依赖前一两层的数据dp 数组可以只保留两层甚至一层。状态压缩把几个独立信息编码成一个整数常见的如二进制状态压缩解决旅行商问题。如果你在做题初期我建议你写完一版正确解之后先跑几个测试用例确认正确再开始做优化。千万不要写完就急着去“高级优化”先把基础的搞扎实。4. 例题详解一0-1背包问题与滚动数组优化0-1 背包问题可以说是动态规划里最经典的入门题。它的题目描述是有一个容量为 W 的背包有 n 件物品每件物品有重量 weight[i] 和价值 value[i]每个物品只能取一次问在不超过背包容量的前提下能装入的最大总价值是多少。解法虽然已经被讨论烂了但它的分析过程包含了动态规划很多核心技巧非常适合拿出来拆开讲。4.1 完整的推导过程第一步穷举分析。假设有 3 件物品背包容量是 5物品1重量1价值15物品2重量3价值20物品3重量4价值30手工试几种装法装物品1和物品2总重量4价值35装物品1和物品3总重量5价值45只装物品3重量4价值30。最优显然是装物品1和物品3价值45。但手工试终究不是办法我们需要一套可程序化执行的推理方式。第二步定义状态。这里引入了第一个难点这个问题有两种天然的状态维度一个是枚举到哪件物品一个是当前背包容量。定义dp[i][j]表示在前 i 件物品中选择每件物品最多选一次放入容量为 j 的背包时能获得的最大价值。第三步推导转移方程。对于第 i 件物品有取和不取两种选择不取dp[i][j] dp[i-1][j]取前提是j weight[i]此时dp[i][j] dp[i-1][j-weight[i]] value[i]综合一下就是dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i]) 当 j weight[i] dp[i][j] dp[i-1][j] 当 j weight[i]为什么这里用的是dp[i-1][j-weight[i]]而不是dp[i][j-weight[i]]因为每件物品只能取一次。如果是完全背包问题每件物品不限次数那就要写成dp[i][j-weight[i]] value[i]意味着在当前这一行里继续放入第 i 件物品。很多初学者第一次看到这两个细节都会懵建议这里反复体会一下。第四步初始化和遍历顺序。dp[0][j] 表示不选任何物品时的价值全为 0。遍历时外层循环物品内层循环容量两层都要从前往后遍历def knapsack_2d(weights, values, W): n len(weights) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, W 1): if j weights[i-1]: dp[i][j] dp[i-1][j] else: dp[i][j] max(dp[i-1][j], dp[i-1][j-weights[i-1]] values[i-1]) return dp[n][W]这里代码中下标要格外注意weights[i-1]是因为 Python 的 list 从 0 开始而 dp 是从 1 开始计数第几件物品这个偏移量是新手最常见的 bug 来源。4.2 滚动数组为什么容量要倒序遍历二维 dp 的时间复杂度是 O(nW)空间复杂度也是 O(nW)。当 n 和 W 都是 10 万级别的时候这个空间是撑不住的。观察转移方程你发现dp[i][j]只依赖dp[i-1]这一层的值跟dp[i-2]及更早的层完全没关系。这意味着我们不需要保存完整的历史表格只需要保存上一行就够了。把 dp 数组从二维压成一维dp[j]代表当前遍历到第 i 件物品时容量为 j 的背包最大价值。如果容量从前往后遍历for i in range(n): for j in range(W 1): if j weights[i]: dp[j] max(dp[j], dp[j - weights[i]] values[i])这在逻辑上是有严重问题的因为你会发现dp[j - weights[i]]可能在当前循环里已经被第 i 件物品覆盖更新过了它不再代表“前 i-1 件物品”的最优值而是“前 i 件物品甚至包含了当前物品”的最优值。这相当于一个物品被重复使用了一次 — 完成了一次“类完全背包”的行为。怎么避免把容量从大到小遍历for i in range(n): for j in range(W, weights[i]-1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i])因为是从大到小更新dp[j - weights[i]]一定还是上一轮前 i-1 件物品的结果还没被当前物品污染过。这个“倒序更新”的原理就是 0-1 背包问题的灵魂操作。在面试里如果你能主动说清楚这点面试官会认为你是真懂了而不是背写法。4.3 为什么初始化还与“恰好装满”有关这里有个很容易被忽略的变体题目问“恰好装满背包的最大价值”和“不超过背包容量时的最大价值”初始化完全不同。求“不超过容量 W”的最大价值时dp[j]全初始化为 0 是对的。因为背包不一定要装满才是合法的从容量 0 的状态开始什么都不装就是合法解。求“恰好装满”的最大价值时dp[0] 0容量 0 恰好装满价值 0而dp[j]j 0应该初始化为负无穷。为什么因为“容量 j 的背包恰好装满”一开始是无法达到的给负无穷才能阻止从这些非法状态转移出看似合理的结果。举个例子如果初始化全是 0背包容量为 5只有一件重量为 3 的物品。在你遍历完这件物品后dp[5]可能会被更新为“重量3物品的价值”它表示容量 5 背包装了重量 3 的东西 — 但容量没满根本不满足“恰好装满”条件。这就错了。这个细节在背包类题里会反复出现建议直接记住这组对比。5. 例题详解二最长递增子序列——从 O(n^2) 到 O(nlogn)第二个例题选最长递增子序列原因有两点一是它的状态定义方式和背包完全不同能帮你拓宽思路二是它包含了一个从 O(n^2) 到 O(nlogn) 的经典时间优化能呼应标题里“算法优化”的部分。5.1 基础版动态规划解法题目给定一个整数数组 nums找到其中最长严格递增子序列的长度。子序列不要求连续但元素在原数组中的相对顺序要保持。先走流程。定义状态dp[i]表示以 nums[i] 结尾的最长递增子序列长度。转移方程遍历 i 之前的所有元素 j如果 nums[j] nums[i]说明 nums[i] 可以接到以 nums[j] 结尾的递增子序列后面那么dp[i]至少是dp[j] 1。取所有可能中的最大值dp[i] max(dp[j] 1) 对所有满足 j i 且 nums[j] nums[i] 的 j如果没有满足条件的 jdp[i] 1即它自己单独组成一个子序列。初始化每个位置的dp[i]都初始化为 1。遍历顺序外层循环枚举 i 从 0 到 n-1内层循环枚举 j 从 0 到 i-1。def length_of_lis(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)这个版本的时间复杂度 O(n^2)空间复杂度 O(n)。在 LeetCode 上提交通常能通过但如果数据量上到 10 万级别O(n^2) 就很难看了。5.2 贪心二分的 O(nlogn) 优化思路O(n^2) 的问题出在哪内层枚举 j 来查“谁比我小”这个动作太慢。如果你仔细观察会发现我们要找的其实是“所有长度合法的递增子序列中末尾元素最小的那一个”。为什么要找末尾最小的因为末尾越小越有利于后续元素接上去形成更长的子序列。于是我们可以维护一个数组 tails其中 tails[k] 表示长度为 k1 的递增子序列中末尾元素的最小值。这个数组一定是严格递增的。遍历每个元素 x在 tails 中做二分查找找到第一个大于等于 x 的位置如果 x 比 tails 末尾还大直接追加说明 x 可以接到目前最长的子序列后面形成更长的一个子序列。否则用 x 替换那个位置的元素相当于“更新”了某个长度下的最小末尾元素为后续元素创造更好的接续可能。代码如下import bisect def length_of_lis(nums): tails [] for x in nums: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)这段代码跑完后tails 的长度就是 LIS 的长度。注意这不是用二分查找直接得出子序列本身要还原具体子序列还需要额外记录但它能高效算出长度。5.3 从这题得到的启发这个例题想让你体会的是动态规划优化的一个核心思路降低内层遍历的维度往往比单纯优化常数更有效。O(n^2) 到 O(nlogn) 是质的提升不是因为代码变短了而是算法复杂度降了一个量级。实际开发中如果数据规模上了百万这种优化就是“能不能跑完”的区别。顺带提一个常见误区tails 数组并不是真实的某个递增子序列。比如 [1, 5, 3] 跑完 tails 可能是 [1, 3]但真实的 LIS 可以是 [1, 5] 或 [1, 3]长度都是 2。tails 只保留“相同长度下的最优末尾”不是为了给你还原整个序列。6. 例题详解三编辑距离——二维动态规划的典型应用编辑距离是字符串处理里的经典动态规划问题也是很多文本比对、代码 diff、语音识别纠错系统的底层基础。它的题目描述是给你两个单词 word1 和 word2你可以对一个单词进行插入、删除、替换三种操作请计算将 word1 转换成 word2 所需的最少操作数。6.1 状态设计和转移方程的从零推导定义状态dp[i][j]表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。接下来分析转移。考虑 word1 的第 i 个字符 w1[i-1] 和 word2 的第 j 个字符 w2[j-1]如果两者相等dp[i][j] dp[i-1][j-1]不需要额外操作。如果两者不等有三种可能操作替换把 w1[i-1] 替换成 w2[j-1]那么dp[i][j] dp[i-1][j-1] 1删除删掉 w1[i-1]让 word1 的前 i-1 个字符和 word2 的前 j 个字符匹配那么dp[i][j] dp[i-1][j] 1插入在 word1 的第 i 个位置后插入一个字符 w2[j-1]让 word1 的前 i 个字符和 word2 的前 j-1 个字符匹配那么dp[i][j] dp[i][j-1] 1综合起来就是dp[i][j] dp[i-1][j-1] 如果 w1[i-1] w2[j-1] dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1 如果 w1[i-1] ! w2[j-1]很多初学者会卡在“插入为什么对应dp[i][j-1]”上。这里的理解关键是插入操作完成后word2 的第 j 个字符已经被“消耗”掉了word1 这边长度不变因为新插的字符就是用来对齐 word2 的第 j 位的所以问题变成了“word1 的前 i 个字符转换到 word2 的前 j-1 个字符”的操作数再加上这次插入。6.2 初始化与遍历顺序的细节dp[0][j]表示空字符串转换成 word2 的前 j 个字符所需的操作数只能通过连续插入 j 次所以dp[0][j] j。dp[i][0]表示 word1 的前 i 个字符转换成空串所需的操作数只能通过连续删除 i 次所以dp[i][0] i。遍历顺序可以从左上往右下逐行推进也可以逐列但必须保证每个状态在计算时其依赖的三个前驱状态都已就绪。def min_distance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1 return dp[m][n]6.3 类似问题的一类变体学会了编辑距离你可以顺带看懂一大类二维字符串动态规划题目最长公共子序列LCSdp[i][j]表示 word1 前 i 个字符与 word2 前 j 个字符的最长公共子序列长度转移逻辑里没有替换操作只有“相等则加一否则取 max(dp[i-1][j], dp[i][j-1])”。最长回文子序列把原串反转求原串与反转串的 LCS。两个字符串的删除操作本质上就是求 LCS 长度然后用两串总长度减去两倍 LCS 长度。你在面试中遇到字符串匹配类问题第一步通常都是从编辑距离这个模型发散出去的。把编辑距离吃透了就等于领到了一张二维动态规划的快车道入场券。7. 动态规划的优化手段与实战注意事项最后一节总结一下动态规划里真正高频使用的优化手段以及一些更偏向工程实战和经验层面的内容。标题里提到了“算法优化”但优化不是炫技每一种优化背后都有对应的问题约束条件。7.1 空间优化滚动数组与状态压缩这个前面已经通过背包问题详细演示过。滚动数组的核心判断标准就一句话当前状态是否只依赖有限层的旧状态。一维问题如果dp[i]只依赖dp[i-1]和dp[i-2]可以用 3 个变量滚动交替。二维问题如果dp[i][j]只依赖dp[i-1][...]这一行可以压成一行数组。如果同时依赖dp[i-1][j]和dp[i][j-1]也就是同一行当前列和上一行的同列那你要小心遍历顺序必要时用一个变量维护“左上角”的旧值。状态压缩则是另一条路线当状态的维度很高但每个维度取值有限时可以用二进制位表示一个集合。典型例子是集合划分和旅行商问题。这种优化思路会让代码的思考难度陡增建议在熟练基础 DP 之后再接触。7.2 时间优化从换数据结构到换状态定义时间优化的层次我做了一个简单的排序从低到高分别是第一层是剪枝去掉那些明显不可能转移到目标状态的情况。比如背包里某个重量已经超过当前容量就直接 skip。这种优化不影响复杂度量级但能明显降低常数。第二层是换数据结构最长递增子序列的例子就是典型 — 用二分查找把 O(n) 的查表操作变为 O(logn)。类似的思想还能用在很多场景比如 DP 转移时需要在一段区间里取 min/max可以用单调队列优化到 O(1)如果有区间求和需求可以配合前缀和。第三层是换状态定义这是最难但也最有趣的一种。比如某些问题把维度从“个数限制”改成“价值维度”问题的复杂度可能从 O(n*K) 降到能跑的范围内。这种思维需要大量练习才能内化。7.3 写代码前的一个习惯小规模用例走一遍最后想分享一个非常实在的习惯。我在实际写动态规划代码前都会选一个小规模的真实数据在纸上或者注释里把 dp 表格先手动填一遍。等填完整张表转移方程里的下标细节、初始化值、遍历方向也就都清楚了代码基本不会出低级错误。这个习惯对初学者尤其有用。很多人一上来就对照题解敲代码看似都懂了但少了“手工推演”这一步脑子里对 dp 表的结构其实是模糊的。面试时如果被要求现场讲题手工推演能力反而更容易打动面试官。7.4 工程中的动态规划不只是刷题虽然这篇文章主要以算法题为载体讲动态规划但它在工程中的应用也同样重要——它是“在约束条件下求最优决策”的数学化表达。比如在嵌入式系统里做能量管理一辆混合动力汽车在不同的行驶工况加速、巡航、爬坡下需要决定发动机和电动机的功率分配目标是油耗最低。这类问题的结构很适合用动态规划求解——把行驶过程按时间切片每个切片的电池电量变化就是状态每两个切片之间的功率分配是决策然后从终点倒推最优策略。再比如 Python 工程里的资源调度、任务队列里的依赖编排、图像处理中的路径寻找如蛇形填数、区域生长都能看到动态规划的影子。所以我建议学动态规划时不要只盯着题解看可以想一想这个状态转移如果放到真实工程里对应的是什么业务决策如果状态变量换成“剩余电池电量”“剩余磁盘空间”“剩余预算”转移方程会怎么变这样学出来的知识才是活的而不是一道一道孤立的题。动态规划是一门“越往后越吃经验”的算法。它的知识点不算多——状态定义、转移方程、边界条件、优化手段翻来覆去就这几个词。但每个词的背后都积累了大量具体问题的处理经验。我的建议是先吃透本文中的三个例题然后把上述五步法刻在脑子里遇到新题就按这个顺序走一遍再逐步扩展到更复杂的题型。过程中踩到的坑—初始化差一个数、遍历顺序反了、状态少了一维—全都会成为你最终理解这座大山的基石。