线性与网格 DP
动态规划 ⭐⭐ 中级 🔥 高频
💡 核心要点
线性 DP 和网格 DP 是最基础的两类 DP。它们的共同特征是：状态沿着固定方向单调推进，每个状态只依赖有限个之前的状态。掌握这两类，你就建立了用 DP 思维解决问题的基本直觉。
第一部分：线性 DP
识别信号
当你看到题目具备以下特征时，优先考虑线性 DP：
- 输入是一维数组或字符串序列
- 问题要求对序列做逐位决策，答案随位置单调推进
- 每个位置的决策只影响"后续"而不影响"之前"——即无后效性
- 典型问句：最大/最小/方案数，且决策是"选还是不选当前元素"或"从哪个前驱跳过来"
反例：如果决策会影响之前的状态（如环形结构），则需要拆成多个线性子问题；如果状态依赖右边的元素，则需要反向 DP 或区间 DP。
通用思考框架
状态定义
线性 DP 的状态通常是 dp[i]，但同样是"前 i 个元素"，有两种完全不同的语义，必须明确区分：
语义 A：dp[i] = 考虑前 i 个元素（可以不选第 i 个）时的最优解
- 这个定义更"宽松"，第 i 个元素不一定参与最终答案
- 转移时可以选择"不动"：
dp[i] = dp[i-1]（跳过第 i 个） - 最终答案直接是
dp[n]，不需要遍历所有 i 取最大值 - 适合：打家劫舍、爬楼梯、解码方法
语义 B：dp[i] = 以第 i 个元素结尾（必须选第 i 个）时的最优解
- 这个定义更"严格"，第 i 个元素一定是子序列/子数组的最后一个
- 好处是转移方程更简洁：枚举前驱 j，
dp[i] = max(dp[j] + ...)for all valid j - 坏处是答案不是
dp[n]，而是max(dp[0..n-1])，因为最优解可能在任意位置结束 - 适合：最大子数组和（Kadane）、最长递增子序列
如何选择？
如果题目限制了相邻元素不能都选（如打家劫舍），或者需要"累积"到位置 i 的历史信息，用语义 A。 如果题目问的是"以某元素结尾的最优子结构"（如连续子数组、递增子序列），用语义 B。
转移方程
确定了状态定义后，问自己：站在位置 i，我有哪些决策？每种决策对应从哪个更小的状态转移来？
线性 DP 的决策模型主要有两种：
模型一：选或不选当前元素
dp[i] = max(
dp[i-1], // 不选第 i 个元素，保持上一个状态
dp[i-2] + nums[i] // 选第 i 个元素（跳过 i-1 避免冲突）
)这是打家劫舍的核心逻辑。关键在于：选了第 i 个，上一个只能是 i-2；不选第 i 个，上一个是 i-1。
模型二：从哪个前驱状态转移
for (int j = 0; j < i; j++) {
if (condition(j, i)) {
dp[i] = max(dp[i], dp[j] + value(i));
}
}枚举所有满足条件的前驱 j，选最优的。这是最长递增子序列（LIS）的思路。时间复杂度通常是 O(n²)，但有时可以用二分优化到 O(n log n)。
模型三：单步转移（斐波那契型）
dp[i] = dp[i-1] + dp[i-2] // 爬楼梯：从 i-1 或 i-2 跳一步过来注意：虽然形式相同，但不同题目含义完全不同。转移方程必须配合状态定义才有意义。
初始化与边界
初始化是转移方程的"地基"——如果地基错了，整栋楼都塌。
思考步骤：
- 找到最小的合法状态（通常是
dp[0]或dp[1]），手动赋值 - 检查转移方程在
i=1时是否能正确用到初始值 - 确认
dp数组的长度：如果下标从 1 开始（dp[1]代表第一个元素），需要n+1长度
常见边界陷阱：
- 打家劫舍：
dp[0]和dp[1]需要特殊处理，因为dp[i-2]在 i=1 时会越界 - 解码方法：空字符串应返回 1（空串有 1 种解码方式），
dp[0] = 1是逻辑上的哨兵值
遍历顺序
线性 DP 几乎都是从左到右遍历，因为 dp[i] 依赖更小下标的状态。
唯一需要思考的是：dp[i] 依赖 dp[i-1] 还是 dp[i-2]？这影响变量的初始化顺序，但不改变"从小到大"这个方向。
空间优化
线性 DP 的空间优化通常很简单：观察转移方程依赖几个历史状态，就保留几个变量。
| 依赖模式 | 优化方式 |
|---|---|
只依赖 dp[i-1] | 用一个变量 prev 滚动 |
依赖 dp[i-1] 和 dp[i-2] | 用两个变量 prev1, prev2 滚动 |
依赖 dp[0..i-1] 中满足条件的（如 LIS） | 无法简单压缩，需要辅助数据结构 |
空间从 O(n) 压缩到 O(1) 是面试加分项，但要先确保 O(n) 版本正确，再做优化。
典型例题：打家劫舍
题目描述
LeetCode 198 — 给定一个整数数组 nums，代表每栋房子的金额。相邻两栋房子不能同时被抢。返回能抢到的最大金额。
示例：nums = [2, 7, 9, 3, 1]，输出 12（抢第 0、2、4 号房子：2+9+1=12）。
思考过程（五步法）
第一步：定义状态
问自己：到第 i 个房子时，我需要知道什么才能做决策？
答：只需要知道"考虑前 i 个房子时能抢到的最大金额"。用语义 A：
dp[i] = 考虑前 i 个房子（下标 0 到 i-1）时能获得的最大金额（不一定抢第 i 个）
为什么不用语义 B（以第 i 个结尾）？因为这里的约束是"相邻不能同时选"，是关于前驱的约束，语义 A 能更自然地表达"跳过"这个决策。
第二步：推导转移方程
站在第 i 个房子，有两个选择：
- 不抢第 i 个：和没有这个房子一样，
dp[i] = dp[i-1] - 抢第 i 个：不能抢第 i-1 个，
dp[i] = dp[i-2] + nums[i-1]（注意下标偏移）
取两者最大值：
第三步：确定初始化
dp[0] = 0：没有房子，金额为 0dp[1] = nums[0]：只有一个房子，抢它
第四步：确定遍历顺序
dp[i] 依赖 dp[i-1] 和 dp[i-2]，从小到大遍历 i 从 2 到 n。
第五步：确定返回值
dp[n]——前 n 个房子的最优解即为答案。
代码实现
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];
// dp[i] = 考虑前 i 个房子能获得的最大金额
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= n; i++) {
// 不抢第 i 个 vs 抢第 i 个（nums[i-1]，下标从0开始）
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[n];
}空间优化版本（O(1) 空间）：
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];
int prev2 = 0; // dp[i-2]
int prev1 = nums[0]; // dp[i-1]
for (int i = 2; i <= n; i++) {
int curr = Math.max(prev1, prev2 + nums[i - 1]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}复杂度分析
- 时间复杂度：O(n)，一次线性遍历
- 空间复杂度：O(n)（原版）/ O(1)（空间优化版）
延伸题目
| 题目 | 链接 | 与典型题的区别 | 关键技巧 |
|---|---|---|---|
| 爬楼梯 | LC 70 | 最基础线性 DP，两个前驱 | 可压缩为两变量 |
| 打家劫舍 II | LC 213 | 环形 → 拆成两个线性子问题 | 分两次 DP：[0, n-2] 和 [1, n-1]，取较大值 |
| 最大子数组和 | LC 53 | dp[i] 定义变化：必须以 i 结尾 | Kadane 算法，dp[i] = max(nums[i], dp[i-1] + nums[i]) |
| 解码方法 | LC 91 | 条件转移，需要判断合法性 | 单字符解码：nums[i] != '0'；双字符解码：10 ≤ val ≤ 26 |
| 跳跃游戏 | LC 55 | 可行性 DP | 维护最远可达位置，若当前位置 > 最远则不可达 |
| 跳跃游戏 II | LC 45 | 最优化：最少跳跃次数 | 贪心更优：每次在当前覆盖范围内选跳得最远的位置 |
常见陷阱与调试（线性 DP）
| 陷阱 | 症状 | 解决方法 |
|---|---|---|
| 混淆语义 A 和语义 B | 答案比正确值小，或最后要多加一个 max 遍历 | 重新用自然语言写下 dp[i] 的含义，对照样例手算 2-3 个值 |
| 初始化时下标偏移出错 | dp[1] 赋的是 nums[1] 而不是 nums[0] | 画出 dp 数组下标与 nums 下标的对应关系 |
| 空间优化后更新顺序错误 | 用新值覆盖了还需要的旧值 | 先算 curr，再更新 prev2 = prev1，最后 prev1 = curr |
| 环形问题未拆分 | 直接对环形数组做线性 DP，首尾同时被选 | 拆成两个子问题：不含最后一个元素，不含第一个元素 |
第二部分：网格 DP
识别信号
当你看到题目具备以下特征时，考虑网格 DP：
- 输入是二维矩阵，需要在网格上移动
- 只允许向有限方向移动（通常是向右或向下，或从某个方向来）
- 求从起点到终点的最优路径值或路径方案数
- 典型问句：最小代价路径、有多少条不同路径
反例：如果可以向四个方向自由移动（如岛屿问题），通常是 DFS/BFS，不是网格 DP。网格 DP 的关键约束是移动方向单一，从而保证无后效性。
通用思考框架
状态定义
网格 DP 的状态定义几乎是固定的：
dp[i][j] = 到达坐标 (i, j) 时的最优解（最小代价 / 最大收益 / 方案数）
这里没有"以 (i,j) 结尾"和"前 i 行 j 列"的歧义，因为路径本身就是从 (0,0) 出发到 (i,j) 的。
例外：地下城游戏（LC 174）需要反向 DP——因为需要知道"到达终点时恰好满足条件"，信息从终点流向起点更自然。
转移方程
只能向右和向下移动时，到达 (i,j) 只有两种来路：
其中 根据题意是 / / 。
最小路径和：
不同路径（计数）：
关键：如果有障碍物，障碍格强制 dp[i][j] = 0（计数型）或 dp[i][j] = Integer.MAX_VALUE（最优型），跳过正常的转移逻辑。
初始化与边界
网格 DP 的初始化比线性 DP 复杂，需要处理第一行和第一列：
- 第一行（
i = 0）：只能从左边来，dp[0][j]只依赖dp[0][j-1] - 第一列（
j = 0）：只能从上边来，dp[i][0]只依赖dp[i-1][0]
初始化过程实际上是：先手动填好第一行和第一列，再用双层循环填其余格子。
有障碍物时：初始化第一行/第一列时，遇到障碍物后面的格子全部无法到达（不能绕过去），要小心"障碍之后的格子"不能被初始化为非零值。
遍历顺序
两层循环，外层行从上到下（i 从小到大），内层列从左到右（j 从小到大）。这样计算 dp[i][j] 时，dp[i-1][j]（上方）和 dp[i][j-1]（左方）都已经算好。
反向 DP（如地下城游戏）：从右下角到左上角遍历，外层行从大到小，内层列从大到小。
空间优化
二维 DP 可以压缩到一维：因为 dp[i][j] 只依赖"上一行相同列"和"当前行前一列"，用一个长度为 n（列数）的一维数组滚动即可。
// 原来：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
// 优化后：dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
// dp[j]（未更新前）代表上一行的 dp[i-1][j]
// dp[j-1]（已更新）代表当前行的 dp[i][j-1]注意更新顺序是从左到右，这样 dp[j-1] 已经是当前行的值，dp[j] 还是上一行的值，恰好符合转移方程的需求。
典型例题：最小路径和
题目描述
LeetCode 64 — 给定一个 m × n 的非负整数网格，找一条从左上角到右下角的路径，使得路径上所有数字之和最小。每次只能向右或向下移动。
示例：
grid = [[1,3,1],
[1,5,1],
[4,2,1]]输出 7，路径为 1 → 3 → 1 → 1 → 1。
思考过程（五步法）
第一步：定义状态
到达 (i,j) 时，我只关心到达这里的最小代价，历史路径不重要（无后效性）。
dp[i][j] = 从 (0,0) 到 (i,j) 的路径最小数字和
第二步：推导转移方程
到达 (i,j) 只有两种方式：从上方 (i-1,j) 向下，或从左方 (i,j-1) 向右。
第三步：确定初始化
- 起点：
dp[0][0] = grid[0][0] - 第一行：只能从左边来，
dp[0][j] = dp[0][j-1] + grid[0][j] - 第一列：只能从上边来，
dp[i][0] = dp[i-1][0] + grid[i][0]
第四步：确定遍历顺序
外层 i 从 1 到 m-1，内层 j 从 1 到 n-1。
第五步：确定返回值
dp[m-1][n-1]，即到达右下角的最小路径和。
代码实现
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
// 起点
dp[0][0] = grid[0][0];
// 第一列：只能从上方来
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 第一行：只能从左方来
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 其余格子
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}空间优化版本（O(n) 空间）：
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
dp[0] = grid[0][0];
for (int j = 1; j < n; j++) {
dp[j] = dp[j - 1] + grid[0][j]; // 初始化第一行
}
for (int i = 1; i < m; i++) {
dp[0] += grid[i][0]; // 每行第一列只能从上方来
for (int j = 1; j < n; j++) {
// dp[j] 此时还是上一行的值（即 dp[i-1][j]）
// dp[j-1] 已经是当前行的值（即 dp[i][j-1]）
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[n - 1];
}复杂度分析
- 时间复杂度：O(m × n)，填满整个 dp 表
- 空间复杂度：O(m × n)（原版）/ O(n)（空间优化版）
延伸题目
| 题目 | 链接 | 与典型题的区别 | 关键技巧 |
|---|---|---|---|
| 不同路径 | LC 62 | 计数型而非最优型 | dp[i][j] = dp[i-1][j] + dp[i][j-1]，第一行第一列全为 1 |
| 不同路径 II | LC 63 | 有障碍物 | 障碍格强制 dp[i][j] = 0，且第一行/列遇障碍后续均为 0 |
| 地下城游戏 | LC 174 | 反向 DP | 从终点往起点推，dp[i][j] = 在 (i,j) 出发需要的最小初始血量 |
| 最大正方形 | LC 221 | dp[i][j] 含义不同 | dp[i][j] = 以 (i,j) 为右下角的最大全 1 正方形的边长；转移：min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 |
常见陷阱与调试（网格 DP）
| 陷阱 | 症状 | 解决方法 |
|---|---|---|
| 忘记初始化第一行/第一列 | dp 表第一行或第一列全为 0，最终答案偏小 | 独立循环初始化第一行和第一列，再进双层循环 |
| 障碍物后的第一行/列未置 0 | 有障碍物的题结果偏大（绕过了实际不可通行的路） | 第一行/列遇到障碍后，后续格子全部设为不可达值并 break |
| 空间优化更新顺序错误 | dp[j-1] 用了上一行的值而不是当前行 | 一维压缩时，j 必须从左到右遍历，保证 dp[j-1] 先更新 |
| 反向 DP 边界条件搞错 | 终点格子初始化有误，导致整体偏移 | 先确定终点的 dp[m-1][n-1]，再推最后一行/列，最后推其余格子 |