1. 从“最优子结构”到“状态转移”动态规划的核心思想动态规划这四个字在算法领域的分量足以让许多初学者望而生畏也让不少面试者闻之色变。但如果你曾为“斐波那契数列”的递归写法超时而烦恼或者面对“背包问题”感觉无从下手那么动态规划正是为你准备的解药。它不是什么高深莫测的魔法而是一种将复杂问题拆解、并聪明地复用中间结果的思维方式。简单来说动态规划的核心就是不要重复计算你已经知道答案的东西。想象一下你要爬一个10级的楼梯每次可以走1级或2级问有多少种不同的走法。如果你用最朴素的递归去算f(10) f(9) f(8)然后f(9) f(8) f(7)……你会发现f(8)被计算了两次f(7)被计算了三次越小的数字被重复计算的次数呈指数级增长。这就是重叠子问题。动态规划的第一块基石就是识别出这类问题并想办法把f(1)到f(10)的结果都存起来下次需要时直接查表。这个“表”就是我们常说的DP表DP Table或备忘录Memoization。光有重叠子问题还不够。动态规划能奏效关键在于最优子结构。意思是一个问题的最优解可以由其子问题的最优解组合得到。比如从A点到C点的最短路径如果经过B点那么这条路径的A到B段必须是A到B的最短路径B到C段也必须是B到C的最短路径。整个问题的最优解完美地分解成了两个子问题的最优解。如果子问题之间相互干扰或者整体最优不能由局部最优简单构成那动态规划就无能为力了。把这两个特性结合起来动态规划的解题框架就清晰了定义状态 - 建立状态转移方程 - 确定边界条件 - 计算顺序填表。状态就是你用DP表要存的东西它描述了问题在某个“阶段”的情况比如“走到第i级台阶的方案数”或“考虑前i个物品、背包容量为j时的最大价值”。状态转移方程则是核心中的核心它严格定义了如何从已知的、更小的子问题的状态推导出当前状态也就是dp[i]和dp[i-1],dp[i-2]等之间的关系。边界条件就是最基础、不可再分的子问题的解比如dp[0]或dp[1]的值。最后按照正确的顺序通常是从小到大去计算并填充整个DP表最终答案就在表的某个位置等着你。接下来我们将通过几个经典到不能再经典的例子把这一套思想彻底掰开揉碎。你会发现无论是面试高频题还是算法竞赛的基础都绕不开它们。2. 入门必修斐波那契数列与爬楼梯——理解重叠子问题让我们从一个最亲切的例子开始重新认识斐波那契数列。它的定义是F(0)0, F(1)1, F(n)F(n-1)F(n-2) (n2)。递归解法一目了然但性能是灾难性的时间复杂度是 O(2^n)因为递归树展开了大量的重复计算。2.1 从递归到“记忆化搜索”第一步优化我们引入一个数组或哈希表来充当备忘录。def fib_memo(n, memo): if n 1: return n # 如果已经计算过直接返回结果 if memo[n] ! -1: return memo[n] # 否则计算并存入备忘录 memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n] def fib(n): memo [-1] * (n 1) return fib_memo(n, memo)这种方法被称为记忆化搜索Memoization它是一种“自顶向下”的动态规划。本质还是递归但通过备忘录避免了重复计算时间复杂度降到了 O(n)。这是理解动态规划“复用结果”思想的绝佳起点。2.2 标准的“自底向上”递推记忆化搜索依赖递归调用栈对于n很大时可能有栈溢出风险。更标准的动态规划是“自底向上”的递推也就是我们常说的填表法。def fib_dp(n): if n 1: return n # 1. 定义DP数组 dp [0] * (n 1) # 2. 初始化边界条件 dp[0], dp[1] 0, 1 # 3. 状态转移与填表 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]这个过程清晰体现了动态规划的步骤定义dp[i]为斐波那契数列第i项的值状态转移方程就是定义本身dp[i] dp[i-1] dp[i-2]边界条件是dp[0]0, dp[1]1计算顺序是从i2一直算到n。2.3 空间优化滚动数组仔细观察计算dp[i]只需要dp[i-1]和dp[i-2]我们根本不需要保存整个数组。这就是状态压缩或滚动数组的思想。def fib_optimized(n): if n 1: return n # 只维护前两个状态 prev, curr 0, 1 # 分别代表 dp[i-2], dp[i-1] for i in range(2, n 1): # 计算新的当前状态 dp[i] next_val prev curr # 滚动更新状态 prev, curr curr, next_val return curr空间复杂度从 O(n) 降到了 O(1)。在很多动态规划问题中尤其是状态只依赖于前有限个状态时这种优化非常常见且有效。爬楼梯问题本质就是斐波那契数列的变种。题目描述一次可以爬1或2个台阶到第n阶有多少种方法。我们定义dp[i]为到第i阶的方法数。要想到达第i阶最后一步要么是从第i-1阶走1步上来要么是从第i-2阶走2步上来。因此到达第i阶的方法数就等于到达第i-1阶的方法数加上到达第i-2阶的方法数。所以状态转移方程同样是dp[i] dp[i-1] dp[i-2]。边界条件是dp[1]1一种方法走一步dp[2]2两种方法两次一步或一次两步。看它和斐波那契数列的递推关系一模一样只是初始项不同。通过这个例子你能深刻体会到定义“状态”的重要性——dp[i]必须精准地表示我们要求解的问题在规模为i时的答案。注意这里有一个初学者极易混淆的点。在爬楼梯问题中为什么dp[0]通常被定义为1从物理意义上理解站在起点第0阶本身就算一种“到达”的方式。这在数学上使得递推式dp[2] dp[1] dp[0] 1 1 2成立符合我们的预期。定义dp[0]1是一个技巧性的边界条件它让代码更简洁。如果你觉得难以理解完全可以从dp[1]和dp[2]开始递推只是循环的起点和边界处理要稍作调整。3. 经典中的经典0-1背包问题——掌握状态定义与转移如果说斐波那契数列是动态规划的“Hello World”那么0-1背包问题就是动态规划的“毕业设计”。它完美地诠释了如何定义二维状态以及状态转移方程中“选择”与“不选择”的决策过程。问题描述有N件物品和一个容量为V的背包。第i件物品的重量是weight[i]价值是value[i]。每件物品只有一件可以选择放或不放入背包。求解将哪些物品装入背包可使总价值最大且不超过背包容量。3.1 状态定义为什么是二维为什么这里不能用一维数组因为问题有两个维度的约束物品的序号和背包的剩余容量。我们不仅要考虑“处理到第几个物品了”还要考虑“在当前容量下能获得的最大价值”。因此最自然的状态定义是dp[i][j]表示从前i个物品中选取放入容量为j的背包中可以得到的最大价值。这里i的范围是[0, N]j的范围是[0, V]。dp[N][V]就是我们要求的最终答案。3.2 状态转移方程决策的艺术对于每个物品i这里i从1开始计数对应物品数组下标i-1面对容量j的背包我们只有两种选择不放入物品i那么问题就退化成了“从前i-1个物品中选容量为j”的子问题。此时的最大价值就是dp[i-1][j]。放入物品i前提是当前背包容量j必须大于等于物品i的重量weight[i-1]。如果放入背包的剩余容量变为j - weight[i-1]并且我们获得了价值value[i-1]。那么此时的最大价值就等于 “物品i的价值” 加上 “从前i-1个物品中选放入剩余容量j - weight[i-1]的背包中的最大价值”即value[i-1] dp[i-1][j - weight[i-1]]。我们的目标是最大化总价值所以状态转移方程就是在这两种决策中取最大值dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i-1]] value[i-1]) 其中当j weight[i-1]时只能选择不放入。3.3 边界条件与填表顺序边界条件当没有物品可选i0或者背包容量为0j0时最大价值自然是0。所以我们可以初始化dp[0][j] 0和dp[i][0] 0。填表顺序由于dp[i][j]依赖于dp[i-1][j]和dp[i-1][j - weight[i-1]]即它依赖于上一行i-1的数据。因此我们必须先遍历物品i从1到N对于每个物品再遍历背包容量j从0到V。在内层循环中j可以从0开始也可以从1开始但当j weight[i-1]时直接继承dp[i-1][j]的值即可。def knapsack_01(N, V, weight, value): # 初始化DP表 (N1) x (V1)全部为0 dp [[0] * (V 1) for _ in range(N 1)] # 开始填表 for i in range(1, N 1): # 遍历物品 w_i weight[i-1] v_i value[i-1] for j in range(0, V 1): # 遍历背包容量 if j w_i: # 当前背包容量装不下物品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) return dp[N][V] # 示例 N 3 V 4 weight [2, 1, 3] value [4, 2, 3] print(knapsack_01(N, V, weight, value)) # 输出6 选物品1和物品2重量3价值63.4 空间优化滚动数组与一维DP观察状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j - w] v)当前第i行的数据只依赖于第i-1行。这意味着我们不需要保存整个N行的表格只需要两行或一行就够了。两行滚动数组使用两个一维数组dp_prev和dp_curr分别代表上一行和当前行。每计算完一个物品就交换它们的角色。这很好理解。更巧妙的一维数组逆向遍历这是背包问题空间优化的精髓。我们只用一个一维数组dp[j]它表示“容量为j的背包所能获得的最大价值”。在遍历物品时我们必须逆序遍历背包容量j从V到0。def knapsack_01_optimized(N, V, weight, value): dp [0] * (V 1) for i in range(N): # 遍历物品 w_i weight[i] v_i value[i] # 关键逆序遍历背包容量 for j in range(V, w_i - 1, -1): dp[j] max(dp[j], dp[j - w_i] v_i) return dp[V]为什么必须逆序因为dp[j]更新时需要用到dp[j - w_i]这个值是“上一轮”即考虑前i-1个物品时的结果。如果正序遍历当更新dp[j]时dp[j - w_i]可能已经在同一轮考虑当前物品i时被更新过了这就相当于物品i被重复放入多次变成了“完全背包”问题。逆序遍历保证了在更新dp[j]时dp[j - w_i]还是“干净”的、未考虑当前物品i的状态。实操心得一维DP写法简洁高效是面试和竞赛中的首选。务必牢记0-1背包一维写法要逆序遍历容量这是核心考点也是极易出错的地方。你可以这样记忆“0-1背包物品唯一状态依赖过去所以要倒着来防止污染。”4. 序列问题典范最长上升子序列LIS——体会“以...结尾”的状态设计最长上升子序列是动态规划处理序列问题的标杆。题目给定一个无序的整数数组nums找到其中最长严格递增子序列的长度。子序列不要求连续。4.1 状态定义固定结尾对于序列问题一个非常有效的状态定义套路是定义dp[i]为以第 i 个元素nums[i]结尾的最长上升子序列的长度。注意这里强制要求子序列必须以nums[i]结尾。为什么这么定义因为这样我们才能建立起状态之间的联系。最终答案不是dp[n-1]而是所有dp[i]中的最大值因为最长子序列不一定以最后一个元素结尾。4.2 状态转移寻找前驱如何求dp[i]既然子序列必须以nums[i]结尾那么我们就需要看看在i之前的所有位置j (0 j i)哪些元素nums[j]比nums[i]小。如果nums[j] nums[i]那么nums[i]就可以接在以nums[j]结尾的上升子序列后面形成一个更长的、以nums[i]结尾的上升子序列。其长度就是dp[j] 1。我们需要遍历所有满足条件的j找到那个能形成最长子序列的即max(dp[j] 1)。如果前面没有比nums[i]小的元素那么以nums[i]结尾的最长上升子序列就是它自己长度为1。因此状态转移方程为dp[i] max(dp[j] 1)对于所有0 j i且nums[j] nums[i]。 如果不存在这样的j则dp[i] 1。4.3 算法实现与复杂度分析def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n # 每个元素本身至少是一个长度为1的子序列 max_length 1 for i in range(1, n): # 遍历 i 之前的所有元素 for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) # 更新全局最大值 max_length max(max_length, dp[i]) return max_length # 示例 nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis(nums)) # 输出4 子序列是 [2, 5, 7, 101] 或 [2, 5, 7, 18]这个算法的时间复杂度是 O(n²)因为对于每个i都需要扫描它之前的所有j。空间复杂度是 O(n)。4.4 优化贪心二分查找O(n log n)标准的O(n²) DP在数据量大时如n10^5会超时。有一个更优的解法其思路是维护一个数组tailstails[k]表示长度为 k1 的所有上升子序列中结尾元素的最小值。这个数组本身是严格递增的为什么因为如果有一个更长的子序列它的结尾元素不可能比一个更短的子序列的结尾元素还小。遍历原数组nums中的每个数x如果x大于tails中的所有元素即大于最后一个元素说明我们可以得到一个更长的上升子序列将x追加到tails末尾。否则在tails中找到第一个大于等于x的元素用x替换它。因为tails是递增的所以可以用二分查找。最终tails的长度就是最长上升子序列的长度。注意tails数组存储的并不一定是真实的LIS但其长度是正确的。def length_of_lis_optimized(nums): tails [] for num in nums: # 二分查找 tails 中第一个 num 的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid # 如果 left 等于 tails 的长度说明 num 比所有都大 if left len(tails): tails.append(num) else: tails[left] num return len(tails)这个算法的时间复杂度是 O(n log n)空间复杂度是 O(n)。它体现了动态规划与贪心、二分查找结合的强大威力。在面试中如果能先讲出O(n²)的DP解法再引出这个优化版本会是非常大的加分项。注意事项LIS的DP解法是理解序列DP的基石。很多变种问题如“最长连续递增序列”、“最长公共子序列”等其状态定义和转移思想都与此一脉相承。务必掌握“以i结尾”这个定义方式它把不确定的结尾固定下来使得状态转移成为可能。5. 动态规划的解题心法与高频变种掌握了几个经典模型我们还需要提炼出通用的解题心法并了解一些常见的变种这样才能在遇到新问题时游刃有余。5.1 动态规划解题四步曲确定状态最关键的一步状态就是DP数组/表里存的东西。问自己两个问题① 问题有哪些变化的维度通常是问题规模如物品个数、序列长度、背包容量等。② 我们需要存什么信息才能描述一个子问题并且能推导出更大规模的问题常见的状态定义有dp[i]以第i个元素结尾的某种最优解如LIS。dp[i][j]涉及两个维度的状态如字符串/序列的前i个和前j个最长公共子序列或者前i个物品容量为j背包问题。dp[i][j][k]三维状态相对少见但存在。推导状态转移方程核心逻辑找出dp[i]或dp[i][j]与之前状态的关系。思考要得到当前状态上一步可能是什么通常涉及“选择”或“决策”。用数学公式清晰地表达这种关系。这是整个动态规划的灵魂也是最难的部分需要大量的练习来培养直觉。初始化边界条件最小的、不可再分的子问题的解是什么通常是dp[0],dp[0][0],dp[i][0],dp[0][j]等。初始化不正确整个递推就会出错。确定计算顺序与输出为了保证在计算当前状态时它所依赖的子问题状态已经被计算出来我们需要确定正确的填表顺序。对于一维DP通常是正序或逆序如背包问题对于二维DP可能是从左到右、从上到下或者斜着遍历。最后答案不一定在dp[n]可能是max(dp[i])或dp[n][m]需要根据问题定义来确定。5.2 常见变种与识别特征完全背包问题与0-1背包的唯一区别是每种物品有无限件。状态转移方程变为dp[i][j] max(dp[i-1][j], dp[i][j - weight[i-1]] value[i-1])。注意在“放入物品i”时依赖的是dp[i][j - w]而不是dp[i-1][j - w]因为放了当前物品后还可以继续放同一种物品。一维优化写法下只需将容量遍历从逆序改为正序即可。# 完全背包一维写法正序遍历容量 for i in range(N): for j in range(weight[i], V 1): # 正序 dp[j] max(dp[j], dp[j - weight[i]] value[i])多重背包问题每种物品有固定的数量s[i]件。最朴素的思路是将其转化为0-1背包把s[i]件物品拆成s[i]个独立的物品但这样复杂度高。优化方法有二进制拆分将s[i]拆分成1,2,4,...2^k, c的组合这些组合可以表示0~s[i]的任何数从而将物品数从s[i]降到log(s[i])和单调队列优化。打家劫舍问题经典的一维线性DP。dp[i]表示考虑前i个房屋能偷窃到的最高金额。状态转移对于第i个房屋有两种选择偷则不能偷i-1金额为dp[i-2] nums[i]或不偷金额为dp[i-1]。取最大值。这是决策类DP的典型。股票买卖问题如买卖一次、无数次、两次、含冷冻期这类问题的状态设计通常需要增加维度来表示“持有状态”。例如dp[i][0]表示第i天结束时不持有股票的最大利润dp[i][1]表示第i天结束时持有股票的最大利润。状态转移方程根据买卖规则、手续费、冷冻期等条件来定义。这是状态机DP的典型。编辑距离两个字符串的经典DP。定义dp[i][j]为将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。操作有插入、删除、替换。状态转移考虑对最后一个字符的操作是这类双序列DP的通用思路。5.3 调试与验证技巧动态规划的代码写出来但结果不对怎么办打印DP表这是最直观的方法。将计算出的DP表完整打印出来与手动模拟的小规模样例进行对比很容易发现哪里计算错误。检查边界初始化dp[0]、dp[0][j]、dp[i][0]是否正确这常常是错误来源。检查状态转移方程对照DP表手动计算某个格子的值看代码逻辑是否与你的数学公式一致。特别注意数组下标是否越界如j - weight[i]可能为负数。检查遍历顺序对于二维DP双重循环的i和j顺序是否正确对于一维背包遍历容量是正序还是逆序动态规划的学习没有捷径核心在于“多练”和“多总结”。从经典的模型入手理解其状态设计和转移的本质然后尝试解决变种问题。每做一道题都要问自己这道题的状态是什么转移方程是什么和哪个经典模型有相似之处久而久之你就能培养出解决问题的“动态规划思维”。