00 专栏导览

动态规划专栏导览：从递归记忆化到面试通关

专栏定位

本专栏面向有一定编程基础、正在备战技术面试的工程师。讨论范围严格限定于动态规划算法这一主题，不涉及图论、并查集、线段树等其他领域。

目标：帮助读者真正理解动态规划的底层思维框架，而非死记硬背状态转移方程。每道题的讲解遵循”是什么 → 为什么出现 → 不这样会怎样 → 如何落地 → 边界与反例”的推导链，力求通俗易懂而不失深度。

---

专栏目录

序号	文章标题	核心话题	覆盖 LeetCode 代表题
01	动态规划思想导论：从暴力递归到记忆化搜索再到 DP 表	DP 三要素、递归树剪枝原理、状态定义与转移方程推导范式	Climbing Stairs、Fibonacci Number、House Robber（引入）
02	一维线性 DP：「选或不选」框架与打家劫舍系列	线性 DP 模板、相邻约束处理、环形数组扩展技巧	House Robber I/II、Delete and Earn
03	背包问题深度解析：0-1 背包、完全背包与空间压缩	二维 DP 推导、滚动数组优化、遍历顺序的本质差异	Partition Equal Subset Sum、Coin Change、Combination Sum IV
04	子序列 DP：最长递增子序列与 $O(n\log n)$ 优化	LIS 状态定义、patience sorting 思想、贪心 + 二分降维	Longest Increasing Subsequence、Russian Doll Envelopes、Longest Bitonic Subsequence
05	最长公共子序列与字符串编辑距离	LCS 二维状态推导、Edit Distance 三方向转移、字符串 DP 通用框架	Longest Common Subsequence、Edit Distance、Interleaving String
06	矩阵路径 DP：网格出发的二维状态转移	路径计数、障碍物初始化陷阱、最小代价路径、三角形变体	Unique Paths I/II、Minimum Path Sum、Triangle、Dungeon Game
07	区间 DP：戳气球、矩阵链乘与「从小区间到大区间」	区间 DP 模板、枚举分割点的正确姿势、回文分割代价	Burst Balloons、Strange Printer、Palindrome Partitioning II
08	字符串 DP 进阶：回文子串、正则与通配符匹配	回文 DP 核心、中心扩展 vs DP、正则匹配的状态机建模	Longest Palindromic Substring、Regular Expression Matching、Wildcard Matching
09	树形 DP 与状态压缩 DP：树上决策与位运算加速	树上选/不选、子树 DP 合并、bitmask 枚举子集	House Robber III、Binary Tree Cameras、Minimum Cost to Connect All Points（状压变体）
10	动态规划综合通关：高频模式识别与面试决策树	六大 DP 模式归类、单调队列优化、斜率优化入门、常见陷阱盘点	Jump Game II、Best Time to Buy and Sell Stock 系列

---

专栏阅读建议

1. 第 01 篇必读：理解”为什么需要 DP”以及”如何系统地推导状态和转移”，后续所有文章都建立在这个基础上
2. 基础线性 DP（02-03）：先掌握最简单的一维和背包问题，建立”定义状态 → 写转移方程 → 确定初始化和遍历顺序”的三步流程
3. 序列 DP（04-05）：子序列类问题是面试高频考点，LIS 的 $O(n\log n)$ 优化和 LCS 必须熟练
4. 二维与区间 DP（06-07）：路径问题是 DP 的入门砖，区间 DP 是进阶门槛，理解「区间长度从小到大枚举」的本质是关键
5. 进阶专题（08-09）：字符串匹配类 DP 和树形 DP 是面试区分度较高的题型，重点理解状态机建模思想
6. 综合总结（10）：用模式识别取代死记硬背，建立面对新题时的决策框架

---

动态规划核心公式速查

问题类型	状态定义	转移方程要点	时间复杂度
一维线性 DP	dp[i] 表示前 $i$ 个元素的最优解	dp[i] = max(dp[i-1], dp[i-2] + val[i])	$O(n)$
0-1 背包	dp[i][j] 表示前 $i$ 件物品、容量 $j$ 的最优解	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)	$O(nW)$
完全背包	同上，但每件物品可取无限次	dp[i][j] = max(dp[i-1][j], dp[i][j-w]+v)	$O(nW)$
LIS	dp[i] 表示以 $a[i]$ 结尾的最长递增子序列长度	dp[i] = max(dp[j]+1) for all j < i, a[j] < a[i]	$O(n^2)$ / $O(n\log n)$
LCS	dp[i][j] 表示 $s_1[\mathrm{0..}i]$ 与 $s_2[\mathrm{0..}j]$ 的 LCS 长度	字符相同则 +1，否则取两方向最大值	$O(mn)$
区间 DP	dp[i][j] 表示区间 $[i,j]$ 的最优解	枚举分割点 $k$: dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + cost)	$O(n^3)$
编辑距离	dp[i][j] 表示 $s_1[\mathrm{0..}i]$ 转化为 $s_2[\mathrm{0..}j]$ 的最小操作数	三种操作取最小值	$O(mn)$
树形 DP	dp[node][0/1] 表示以 node 为根、选/不选 node 的最优解	DFS 后序遍历合并子节点状态	$O(n)$
状态压缩 DP	dp[mask] 表示已选集合为 mask 时的最优解	枚举 mask 的子集	$O(2^n\cdot n)$

---

本专栏不覆盖的内容

• 图论 DP（最短路、DAG 上的 DP）：本质是图算法，不属于纯 DP 专题
• 数位 DP：属于竞赛进阶内容，面试极少考察
• 概率 DP：属于数学期望问题，超出面试通常范围
• 博弈论 DP（Nim 游戏等）：属于组合博弈论，单独成专题更合适