第 23 站 · 动态规划
网格路径与二维状态
网格 DP 压成一行 时间 O(行数 × 列数) · 空间 O(列数)
- 先学
- 学完去
- 没有后续站依赖它。
- 面试频次
- 2 家公司考过 · 面经出现 2 次Goldman Sachs 1、Upstart 1
先做这道
LC 62不同路径卡住再看
用二维坐标表示路径计数，处理第一行、第一列和滚动数组。
要点
- dp[r][c] 只依赖上方和左方，按行从左到右填，一行数组就够：更新前 dp[c] 是上方，dp[c-1] 是左方。
- 第一行、第一列只有一个来源，要么单独处理，要么用无穷大哨兵统一写法。
- 路径计数就把 min 换成加法；有障碍的格子直接置 0。
易错点
- 哨兵用 INT_MAX 再加上格子值会溢出，要保证只在有限值上做加法。
- 允许往四个方向走时没有填表顺序，DP 不成立，要用 BFS 或 Dijkstra。
- 压成一行之后，如果转移还需要左上角的值，要在它被覆盖前先存到变量里。
看动画
一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。
二维 DP · 填表求最长公共子序列
「ACBD」和「ABCD」的最长公共子序列
换个输入
∅
A
B
C
D
∅
00,0
00,1
00,2
00,3
00,4
A
01,0
·1,1
·1,2
·1,3
·1,4
C
02,0
·2,1
·2,2
·2,3
·2,4
B
03,0
·3,1
·3,2
·3,3
·3,4
D
04,0
·4,1
·4,2
·4,3
·4,4
当前处理已发现 / 已计算答案
- LCS 长度
- —
dp[i][j] 是「ACBD」前 i 个字符与「ABCD」前 j 个字符的最长公共子序列长度。第 0 行和第 0 列是空串，都为 0。
始终成立按行从左到右填：算 dp[i][j] 时，它依赖的上方、左方、左上方都已算好。
模板
选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 62。
Python
def min_path_sum(grid: list[list[int]]) -> int:
"""Cheapest path from top-left to bottom-right moving only right or down."""
cols = len(grid[0])
dp = [float("inf")] * cols # before row r is filled, dp[c] holds row r-1
dp[0] = 0
for row in grid:
for c in range(cols):
left = dp[c - 1] if c else float("inf")
dp[c] = min(dp[c], left) + row[c] # from above (old dp[c]) or the left (new dp[c-1])
return dp[-1]C++
// Cheapest path from top-left to bottom-right moving only right or down.
int minPathSum(const vector<vector<int>>& grid) {
int cols = grid[0].size();
vector<int> dp(cols, INT_MAX); // before row r is filled, dp[c] holds row r-1
dp[0] = 0;
for (auto& row : grid)
for (int c = 0; c < cols; c++) {
int best = c ? min(dp[c], dp[c - 1]) : dp[c]; // from above or from the left
dp[c] = best + row[c]; // best is always finite here
}
return dp[cols - 1];
}Java
class Solution {
// Cheapest path from top-left to bottom-right moving only right or down.
int minPathSum(int[][] grid) {
int cols = grid[0].length;
int[] dp = new int[cols]; // before row r is filled, dp[c] holds row r-1
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int[] row : grid)
for (int c = 0; c < cols; c++) {
int best = c > 0 ? Math.min(dp[c], dp[c - 1]) : dp[c]; // from above or the left
dp[c] = best + row[c]; // best is always finite here
}
return dp[cols - 1];
}
}Go
import "math"
// minPathSum returns the cheapest path from top-left to bottom-right moving only right or down.
func minPathSum(grid [][]int) int {
cols := len(grid[0])
dp := make([]int, cols) // before row r is filled, dp[c] holds row r-1
for c := 1; c < cols; c++ {
dp[c] = math.MaxInt
}
for _, row := range grid {
for c := range row {
best := dp[c]
if c > 0 {
best = min(best, dp[c-1]) // from above or from the left
}
dp[c] = best + row[c] // best is always finite here
}
}
return dp[cols-1]
}常见变体
这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。
最大正方形：取上、左、左上三者最小再加一时间 O(rows × cols) · 空间 O(cols)
求全 1 的最大正方形（或统计正方形个数）：dp 是「以 (r, c) 为右下角的最大边长」，它被上、左、左上三个方向里最短的那个限制住，所以是三者最小值加一。压成一行时用一个变量保存左上角的旧值。LC 221 最大正方形、LC 1277 统计全为 1 的正方形子矩阵。
Python
def maximal_square(matrix: list[str]) -> int:
"""Area of the largest all-'1' square; each row is a string such as "10111" (LC 221)."""
cols = len(matrix[0])
dp = [0] * (cols + 1) # dp[c + 1]: side of the largest square ending at (r, c); dp[0] stays 0
best = 0
for row in matrix:
diag = 0 # the up-left neighbour: dp[c] before this row overwrote it
for c in range(cols):
up = dp[c + 1]
dp[c + 1] = min(up, dp[c], diag) + 1 if row[c] == "1" else 0 # limited by up, left, up-left
best = max(best, dp[c + 1])
diag = up
return best * bestC++
// Area of the largest all-'1' square; each row is a string such as "10111" (LC 221).
int maximalSquare(const vector<string>& matrix) {
int cols = matrix[0].size(), best = 0;
vector<int> dp(cols + 1, 0); // dp[c + 1]: side of the largest square ending at (r, c); dp[0] stays 0
for (const string& row : matrix) {
int diag = 0; // the up-left neighbour: dp[c] before this row overwrote it
for (int c = 0; c < cols; c++) {
int up = dp[c + 1];
dp[c + 1] = row[c] == '1' ? min({up, dp[c], diag}) + 1 : 0; // limited by up, left, up-left
best = max(best, dp[c + 1]);
diag = up;
}
}
return best * best;
}Java
class Solution {
// Area of the largest all-'1' square; each row is a string such as "10111" (LC 221).
int maximalSquare(String[] matrix) {
int cols = matrix[0].length(), best = 0;
int[] dp = new int[cols + 1]; // dp[c + 1]: side of the largest square ending at (r, c); dp[0] stays 0
for (String row : matrix) {
int diag = 0; // the up-left neighbour: dp[c] before this row overwrote it
for (int c = 0; c < cols; c++) {
int up = dp[c + 1];
dp[c + 1] = row.charAt(c) == '1' ? Math.min(Math.min(up, dp[c]), diag) + 1 : 0; // limited by up, left, up-left
best = Math.max(best, dp[c + 1]);
diag = up;
}
}
return best * best;
}
}Go
// maximalSquare returns the area of the largest all-'1' square; each row is a string (LC 221).
func maximalSquare(matrix []string) int {
cols, best := len(matrix[0]), 0
dp := make([]int, cols+1) // dp[c + 1]: side of the largest square ending at (r, c); dp[0] stays 0
for _, row := range matrix {
diag := 0 // the up-left neighbour: dp[c] before this row overwrote it
for c := 0; c < cols; c++ {
up := dp[c+1]
if row[c] == '1' {
dp[c+1] = min(up, dp[c], diag) + 1 // limited by up, left, up-left
} else {
dp[c+1] = 0
}
best = max(best, dp[c+1])
diag = up
}
}
return best * best
}从终点倒着推的网格 DP时间 O(rows × cols) · 空间 O(cols)
起点的需求取决于后面会发生什么（地下城游戏要「全程血量 ≥ 1」）时，正着推缺信息：从右下角倒推「进入这一格时至少要多少」，取右边和下边较小的需求，减去本格的增减，再和 1 取大。LC 174 地下城游戏；LC 120 三角形最小路径和自底向上也是倒推。
Python
def min_initial_health(dungeon: list[list[int]]) -> int:
"""Least starting health to reach the bottom-right keeping health >= 1 throughout (LC 174)."""
rows, cols = len(dungeon), len(dungeon[0])
need = [float("inf")] * (cols + 1) # need[c]: least health on entering (r, c)
need[cols - 1] = 1 # a virtual cell below the goal: arrive there with at least 1
for r in range(rows - 1, -1, -1):
for c in range(cols - 1, -1, -1):
nxt = min(need[c], need[c + 1]) # down (row r + 1's value) or right (already row r)
need[c] = max(1, nxt - dungeon[r][c])
return need[0]C++
// Least starting health to reach the bottom-right keeping health >= 1 throughout (LC 174).
int minInitialHealth(const vector<vector<int>>& dungeon) {
int rows = dungeon.size(), cols = dungeon[0].size();
vector<int> need(cols + 1, INT_MAX); // need[c]: least health on entering (r, c)
need[cols - 1] = 1; // a virtual cell below the goal: arrive there with at least 1
for (int r = rows - 1; r >= 0; r--)
for (int c = cols - 1; c >= 0; c--) {
int next = min(need[c], need[c + 1]); // down (row r + 1's value) or right (already row r)
need[c] = max(1, next - dungeon[r][c]);
}
return need[0];
}Java
class Solution {
// Least starting health to reach the bottom-right keeping health >= 1 throughout (LC 174).
int minInitialHealth(int[][] dungeon) {
int rows = dungeon.length, cols = dungeon[0].length;
int[] need = new int[cols + 1]; // need[c]: least health on entering (r, c)
Arrays.fill(need, Integer.MAX_VALUE);
need[cols - 1] = 1; // a virtual cell below the goal: arrive there with at least 1
for (int r = rows - 1; r >= 0; r--)
for (int c = cols - 1; c >= 0; c--) {
int next = Math.min(need[c], need[c + 1]); // down (row r + 1's value) or right (already row r)
need[c] = Math.max(1, next - dungeon[r][c]);
}
return need[0];
}
}Go
// minInitialHealth returns the least starting health that keeps health >= 1 to the bottom-right (LC 174).
func minInitialHealth(dungeon [][]int) int {
rows, cols := len(dungeon), len(dungeon[0])
need := make([]int, cols+1) // need[c]: least health on entering (r, c)
for c := range need {
need[c] = 1 << 60
}
need[cols-1] = 1 // a virtual cell below the goal: arrive there with at least 1
for r := rows - 1; r >= 0; r-- {
for c := cols - 1; c >= 0; c-- {
next := min(need[c], need[c+1]) // down (row r + 1's value) or right (already row r)
need[c] = max(1, next-dungeon[r][c])
}
}
return need[0]
}为什么对
- 到达 (r, c) 的最后一步只能来自上方或左方，两类互不相交，所以最小路径和 = 格子值 + min(上, 左)，路径数 = 上 + 左。
- 一维压缩为什么对：按行从左到右更新，更新 dp[c] 之前它还是上一行的值（上方），dp[c−1] 已经是本行的新值（左方），正好是转移需要的两个值。
30 秒口述稿
面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。
网格 DP 里，到达一个格子的最后一步只能从上面或左边来，所以 dp[r][c] 等于格子值加上上方和左方里更小的那个；计数题就把两者相加，障碍格设为 0。第一行和第一列只有一个来源，单独初始化或者用无穷大做哨兵。空间可以压到一行：从左往右更新时，dp[c] 更新前是上方的值，dp[c−1] 已经是左方的新值。时间 O(行 × 列)，空间 O(列)。In grid DP the last step into a cell comes from above or from the left, so dp[r][c] is the cell value plus the smaller of those two; for counting I add them instead and set obstacles to zero. The first row and column have only one source, so I initialise them separately or use an infinity sentinel. One row of memory is enough: filling left to right, dp[c] still holds the value above, and dp[c − 1] already holds the new value to the left. That is O(rows × cols) time and O(cols) space.自评一下
对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。 只存在这台设备上；登录后会合并到你的账号。
小测
3 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。 去 OA 选择题练习
作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。
模板练习
用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。
下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。
分档练习
本站在 500 路里的 8 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。
基础 1
| # | 题目 | 一句话思路 | 难度分 |
|---|---|---|---|
| 62 | 不同路径 | 用二维坐标表示路径计数，处理第一行、第一列和滚动数组。 |
核心 6
进阶 1
| # | 题目 | 一句话思路 | 难度分 |
|---|---|---|---|
| 174 | 地下城游戏 | 从终点反推最低生命值，说明只记录前向累计和为何不足以得到可行答案。 |
本站 OA 真题 13
- Cave AdvantureMeta
- Minimum Merge ConflictsAmazon
- Optimal Path in a GridMicrosoft
- Airport Limousine (Maximum Passengers Collected) (Also for Core/Database Intern :)Snowflake
- Count RoutesUber
- Maximal Square AreaUber
- Find Longest Diagonal SegmentRoblox
- Maximum Reward (Intuit India)Intuit
- Escape the Haunted Castle (Part 2)Sentry
- Matrix TraversalFlexport