LeetCode 动态规划十大核心模型全景大一统背包/区间/树形/状压/数位/斜率优化在整个计算机算法大厦与 LeetCode 刷题体系中“动态规划Dynamic ProgrammingDP”无论是从题目出现的频率、解法的精妙程度还是在区分普通选手与顶级算法专家的能力维度上都是当之无愧的“算法之王”。许多初学者在学习动态规划时常常感觉“题目千变万化做了一百道依然没有章法”。然而只要站在高维度的数学建模视角俯瞰整个 LeetCode 平台上的上千道动态规划题目在底层状态转移与拓扑结构上全部可以归纳收敛为【十大经典核心模型】今天我们在 9 月算法专栏的巅峰收官之际把动态规划的三大公理要素、十大核心模型判定树、状态转移方程全景矩阵与模板做一次终极全景大一统总结。动态规划十大核心模型全景决策树graph TD Start[动态规划问题] -- Dim{状态维度与拓扑依赖特征} Dim --|线性序列从前向后递推| LinearFamily{序列依赖模式} LinearFamily --|单序列 / 数组子段 / 股票买卖| LinearDP[1. 基础线性与多状态机 DP (如 LIS, 最大子数组和)] LinearFamily --|双序列比对 / 编辑距离 / LCS| DoubleDP[2. 双序列匹配 DP (如 LCS, 编辑距离)] LinearFamily --|资源容量限制与物品选取| Knapsack[3. 背包问题家族 (0-1背包 / 完全背包 / 多重背包)] Dim --|连续子区间合并与分割 (两端向内收敛)| Interval[4. 区间 DP (如 石子合并 / 最长回文子串 / 戳气球)] Dim --|树形拓扑结构与父子节点决策| TreeDP[5. 树形 DP (如 树的直径 / 打家劫舍 III / 树上最大独立集)] Dim --|离散集合状态压缩 / N 20| StateComp[6. 状态压缩 DP (如 旅行商问题 TSP / 蒙德里安的梦想)] Dim --|超大数字区间统计 [L, R] / R 10^18| DigitDP[7. 数位 DP (如 数字 1 的个数 / 无重复数字排列)] Dim --|高阶状态转移与代数/几何加速优化| AdvOpt{优化模型} AdvOpt --|单调性队列优化 1D/1D| MonoQ[8. 单调队列优化 DP (如 滑动窗口最值 / 多重背包二进制拆分)] AdvOpt --|点斜式方程与下凸壳维护| SlopeOpt[9. 斜率优化 DP (Convex Hull Trick)] AdvOpt --|带权二分降维 / 限制恰好 K 个子段| WqsOpt[10. WQS 二分 / 斜率二分 DP]一、动态规划三大底层公理要素无论属于哪一种模型一个合法的动态规划解法必须满足三大基本公理最优子结构Optimal Substructure原问题的全局最优解必然由子问题的局部最优解组合而成无后效性No-Aftereffect当前状态一旦确定其后续的发展只取决于当前状态的值与“过去是如何一步步到达该状态的历史路径”完全无关重叠子问题Overlapping Subproblems在递归展开过程中相同的子状态会被反复计算因此必须通过“数组表格Tabulation”或“记忆化缓存Memoization”避免重复计算。二、动态规划十大核心模型状态转移全景矩阵模型分类典型 LeetCode 题目核心状态定义与物理含义标准状态转移方程核心优化手段1. 基础线性 DP300. 最长递增子序列198. 打家劫舍$dp[i]$以第 $i$ 个元素结尾的最优解$dp[i] \max_{j i, \text{nums}[j] \text{nums}[i]} (dp[j] 1)$贪心 树状数组 / 二分 $\mathcal{O}(N \log N)$2. 双序列匹配 DP1143. 最长公共子序列72. 编辑距离$dp[i][j]$文本 1 前 $i$ 个字符与文本 2 前 $j$ 个字符的匹配最优解$dp[i][j] \begin{cases} dp[i-1][j-1] 1 \text{若 } s_1[i] s_2[j] \ \max(dp[i-1][j], dp[i][j-1]) \text{否则} \end{cases}$滚动数组空间压缩 $\mathcal{O}(M)$3. 背包家族 DP416. 分割等和子集322. 零钱兑换$dp[i][w]$前 $i$ 种物品在容量 $w$ 下的最优解$dp[w] \max(dp[w], dp[w - \text{cost}] \text{val})$0-1 背包倒序遍历完全背包正序遍历4. 区间 DP312. 戳气球516. 最长回文子序列$dp[i][j]$区间 $[i, j]$ 内的最优解$dp[i][j] \max_{i \le k \le j} (dp[i][k-1] dp[k1][j] \text{cost})$严格按区间长度 $\text{len} 2 \dots N$ 从小到大遍历5. 树形 DP337. 打家劫舍 III124. 二叉树最大路径和$dp[u][0/1]$节点 $u$ 选或不选时子树的最优解$dp[u][0] \sum \max(dp[v][0], dp[v][1]), \ dp[u][1] \text{val}[u] \sum dp[v][0]$树上自底向上后序遍历DFS6. 状态压缩 DP847. 访问所有节点最短路径TSP 旅行商问题$dp[\text{mask}][u]$已访问集合 $\text{mask}$ 且当前停留在点 $u$$dp[\text{mask} \mid (1 \ll v)][v] \min (dp[\dots], dp[\text{mask}][u] \text{dist}[u][v])$32 位整型二进制位运算,7. 数位 DP233. 数字 1 的个数1012. 至少有 1 位重复dfs(index, state, isLimit, isNum)前缀差分 $\text{Count}([L, R]) \text{solve}(R) - \text{solve}(L-1)$!isLimit isNum记忆化搜索8. 单调队列优化239. 滑动窗口最大值多重背包二进制拆分$dp[i] \min_{i-k \le j i} (dp[j] \dots)$队头剔除过期队尾淘汰非最优值双端队列Deque均摊 $\mathcal{O}(N)$9. 斜率优化 DP任务安排问题3117. 划分数组最小代价$y_j k_i x_j b_i$点斜式将最值决策点映射为二维平面下凸壳切点单调队列维护下凸壳割线斜率 $\mathcal{O}(N)$10. WQS 二分 DP限制恰好选 $K$ 个子区间的代价极值引入惩罚因子 $\lambda$二分斜率将限制条件消除$g(\lambda) \min (dp[n] - k \lambda)$凸函数二分斜率 $\mathcal{O}(N \log C)$动态规划通关解题五步法金字塔graph TD Step1[第 1 步: 确立物理状态定义 (明确 dp 数组每一个下标维度的物理含义)] -- Step2[第 2 步: 推导状态转移方程 (从最后一步决策出发, 寻找子问题递推因果)] Step2 -- Step3[第 3 步: 明确初始边界条件与非法值 (Base Cases: 0 / INF / -INF)] Step3 -- Step4[第 4 步: 确定严格的遍历拓扑顺序 (保证计算当前状态时, 所依赖的所有子状态早已计算完成!)] Step4 -- Step5[第 5 步: 空间复杂度压缩与高阶代数优化 (滚动数组 / 单调队列 / 凸包斜率)]实习生的算法大一统感悟动态规划的本质是**“用空间记录历史用递推消除冗余用代数与拓扑秩序征服组合爆炸”**。从最朴素的斐波那契数列到双序列的二维矩阵从树形图上的递归收集再到多面体凸包上的斜率漫步十大模型犹如十面精密的水晶棱镜将现实世界中无数复杂的决策路径折射为清晰的数学递推。掌握了动态规划的十大核心模型大一统体系你便拥有了通关 LeetCode 算法体系最核心的万能钥匙。
