从OpenCV到dlib：基于EAR的实时疲劳检测完整实现
2026/9/30 1:28:06
LeetCode 动态规划十大核心模型全景大一统（背包/区间/树形/状压/数位/斜率优化）
在整个计算机算法大厦与 LeetCode 刷题体系中，“动态规划（Dynamic Programming，DP）”无论是从题目出现的频率、解法的精妙程度，还是在区分普通选手与顶级算法专家的能力维度上，都是当之无愧的“算法之王”。
许多初学者在学习动态规划时，常常感觉“题目千变万化，做了一百道依然没有章法”。
然而，只要站在高维度的数学建模视角俯瞰：
整个 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. 基础线性 DP | 300. 最长递增子序列 198. 打家劫舍 | $dp[i]$：以第 $i$ 个元素结尾的最优解 | $dp[i] = \max_{j < i, \text{nums}[j] < \text{nums}[i]} (dp[j] + 1)$ | 贪心 + 树状数组 / 二分 $\mathcal{O}(N \log N)$ |
| 2. 双序列匹配 DP | 1143. 最长公共子序列 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. 背包家族 DP | 416. 分割等和子集 322. 零钱兑换 | $dp[i][w]$：前 $i$ 种物品在容量 $w$ 下的最优解 | $dp[w] = \max(dp[w], dp[w - \text{cost}] + \text{val})$ | 0-1 背包倒序遍历，完全背包正序遍历 |
| 4. 区间 DP | 312. 戳气球 516. 最长回文子序列 | $dp[i][j]$：区间 $[i, j]$ 内的最优解 | $dp[i][j] = \max_{i \le k \le j} (dp[i][k-1] + dp[k+1][j] + \text{cost})$ | 严格按区间长度 $\text{len} = 2 \dots N$ 从小到大遍历 |
| 5. 树形 DP | 337. 打家劫舍 III 124. 二叉树最大路径和 | $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]$ | 树上自底向上后序遍历（DFS） |
| 6. 状态压缩 DP | 847. 访问所有节点最短路径 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. 数位 DP | 233. 数字 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 算法体系最核心的万能钥匙。