线性 dp 是什么？
- 定义: 阶段划分具有线性顺序的动态规划方法;
- 特点: 状态按输入的下标顺序推进, 转移只依赖序号更小的状态;
- 分类依据: 输入的形状决定状态维度;
- 四类: 单串、双串、矩阵、无串;
子数组和子序列的状态定义有什么区别？
| 概念 | 是否连续 | 常用状态 |
|---|
| 子数组 | 连续 | 以 nums[i] 结尾 |
| 子序列 | 可不连续 | 前 i 个元素 |
| 子串 | 连续 | 以 s[i] 结尾或 [i, j] |
| 子序列(串) | 可不连续 | 前 i / 前 j 个前缀 |
- 连续约束: 状态必须锚定右端点, 断开时状态归零或重置;
- 非连续约束: 状态只看前缀长度, 允许跳过当前元素;
单串问题的状态怎么定义？
- 输入: 单个数组或单个字符串;
- 状态: 一般为
dp[i];
- 两种口径:
- 以
nums[i] 结尾的子数组相关状态 (适合连续问题);
- 前
i 个元素的相关状态 (适合子序列、划分问题);
- 典型: 最长递增子序列、字符串划分 dp;
双串问题的状态怎么定义？
- 输入: 两个数组或两个字符串;
- 状态: 一般为
dp[i][j];
- 含义:
nums1 前 i 个元素与 nums2 前 j 个元素的匹配、编辑或公共部分;
- 下标习惯: 用
i-1、j-1 访问字符, 给空串留出 dp[0][*]、dp[*][0];
- 典型: 最长公共子序列、编辑距离;
矩阵问题的状态怎么定义？
- 输入: 二维矩阵;
- 状态:
dp[i][j] 表示从 [0, 0] 到 [i, j] 的路径、代价或形状属性;
- 转移方向: 只从上方、左方 (偶有左上方) 迁入, 保证填表时依赖已就绪;
- 典型: 不同路径、最大正方形;
无串线性 dp 是什么？
- 定义: 输入不是显式的数组、字符串或矩阵, 但能分解为线性阶段子问题的 dp;
- 例: 鸡蛋掉落按"次数 × 鸡蛋数"推进, 圆环回原点按"步数 × 位置"推进;
- 处理方式: 先自行构造阶段变量, 再套四步;
- 见 鸡蛋掉落、圆环回原点;