1. 动态规划核心思想拆解第一次接触动态规划时我被状态转移方程这个概念吓得不轻。直到后来用爬楼梯的例子反复琢磨才发现DP本质上就是用空间换时间的暴力穷举优化。举个例子计算斐波那契数列时普通递归会有大量重复计算比如fib(5)会重复计算fib(3)而DP通过数组存储中间结果避免了这种浪费。动态规划三要素中重叠子问题最容易理解——就像做数学题时反复用到同一个公式。最优子结构则像搭积木全局最优解必须由局部最优解构成比如最短路径的子路径也必须最短。最关键的状态转移方程其实就是递推关系的数学表达比如经典的背包问题dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])实际解题时我习惯用三步走策略定义状态明确dp[i]或dp[i][j]代表什么比如走到第i阶的方法数建立转移关系思考当前状态如何由前序状态推导比如dp[i] dp[i-1] dp[i-2]确定边界条件给初始状态赋值比如dp[0]1, dp[1]12. 一维DP经典题型实战2.1 爬楼梯问题变形青蛙跳台阶问题LeetCode 70是最经典的入门题。但实际面试中我遇到过更复杂的变种每次可以跳1~k阶。这时候状态转移方程就变成了dp[n] dp[n-1] dp[n-2] ... dp[n-k]有个容易踩的坑是初始值设置。当k3时正确的初始化应该是dp[0] 1 # 地面算1种方案 dp[1] 1 dp[2] dp[1] dp[0]2.2 打家劫舍系列这个系列完美展示了DP的灵活性。基础版LeetCode 198的状态转移很简单dp[i] max(dp[i-1], dp[i-2] nums[i])但到了环形社区版LeetCode 213就需要分两种情况处理抢第一家就不能抢最后一家计算nums[0:n-1]不抢第一家可以抢最后一家计算nums[1:n]我曾在周赛中遇到过更复杂的树形版本LeetCode 337这时候就需要用后序遍历来处理树形DP。3. 二维DP高频场景剖析3.1 网格路径问题机器人路径问题LeetCode 62的解法看似简单dp[i][j] dp[i-1][j] dp[i][j-1]但实际项目中我遇到过带障碍物的变种LeetCode 63。这时候需要在初始化第一行/列时特别注意一旦遇到障碍物后面的格子都不可达。代码处理如下for i in range(m): if obstacleGrid[i][0] 1: break dp[i][0] 13.2 字符串编辑距离这道题LeetCode 72的状态设计非常巧妙if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min( dp[i-1][j], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1] # 替换 )我在实际开发中曾用类似的思路实现过代码差异对比工具。关键是要理解当字符相同时无需操作直接继承左上角的值不同时三种操作对应着不同的状态转移方向4. 背包问题深度解析4.1 01背包的优化技巧标准的01背包代码大家都会写for i in range(n): for j in range(W, w[i]-1, -1): dp[j] max(dp[j], dp[j-w[i]] v[i])但很多人不知道倒序遍历容量的原因正序会导致物品被重复计算变成完全背包。我做过一个实验用w[2,3], v[4,5], W5测试正序得到错误结果9相当于物品用了多次倒序得到正确结果74.2 完全背包的排列组合完全背包LeetCode 518有个易错点求组合数时要先遍历物品求排列数时要先遍历容量。以零钱兑换为例# 组合数解法 for coin in coins: for i in range(coin, amount1): dp[i] dp[i-coin] # 排列数解法 for i in range(1, amount1): for coin in coins: if coin i: dp[i] dp[i-coin]这个差异我在面试候选人时经常考察能很好检验对DP本质的理解。5. 状态压缩与优化策略5.1 滚动数组技巧当状态只依赖前几个值时可以用模运算压缩空间。比如斐波那契数列dp [0, 1, 1] for i in range(3, n1): dp[i%3] dp[(i-1)%3] dp[(i-2)%3]在解决棋盘类DP时如LeetCode 576这个技巧能节省大量内存。我曾用这个方法将空间复杂度从O(mnk)降到O(mn)。5.2 位运算状压处理状态较少的DP时如LeetCode 464可以用二进制位表示状态mask 0 # 初始状态 mask | 1 i # 标记第i位已访问 if mask (1 j): # 检查第j位这类题的关键是找到状态编码方式。我总结的经验是每个状态变量不超过20种可能时因为2^20≈百万适合用位压缩。6. 动态规划调试方法论调试DP代码时我常用的三板斧打印DP表用二维数组可视化中间结果for row in dp: print([f{x:2d} for x in row])边界检查特别注意i0或j0时的初始化逆向推导从结果反推状态转移是否正确有次做周赛题LeetCode 174我因为没处理负数值导致WA。后来在DP表中加入偏移量才解决offset sum([abs(x) for row in dungeon for x in row]) dp[i][j] max(1, min(dp[i1][j], dp[i][j1]) - dungeon[i][j])7. 从模板到思维的跃迁经过大量练习后我发现DP题可以分为几类套路序列型LIS/LCS通常dp[i]表示以i结尾的最优解区间型石子合并dp[i][j]表示区间[i,j]的最优解状态机型股票买卖用多个状态表示持有/未持有等但真正的高手应该超越模板。比如最近遇到的一道题给定数组求子序列异或和的最大值。看似像背包问题但实际需要按位处理max_xor 0 mask 0 for i in range(30, -1, -1): mask | 1 i prefixes {num mask for num in nums} candidate max_xor | (1 i) for p in prefixes: if (p ^ candidate) in prefixes: max_xor candidate break这种题就需要结合位运算知识不能生搬硬套DP模板。建议大家在掌握基础后多尝试AtCoder上的思维题培养问题转化能力。