14.3 动态规划解题思路¶
上两节介绍了动态规划问题的主要特征,接下来我们一起探究两个更加实用的问题。
- 如何判断一个问题是不是动态规划问题?
- 求解动态规划问题该从何处入手,完整步骤是什么?
14.3.1 问题判断¶
总的来说,如果一个问题包含重叠子问题、最优子结构,并满足无后效性,那么它通常适合用动态规划求解。然而,我们很难从问题描述中直接提取出这些特性。因此我们通常会放宽条件,先观察问题是否适合使用回溯(穷举)解决。
适合用回溯解决的问题通常满足“决策树模型”,这种问题可以使用树形结构来描述,其中每一个节点代表一个决策,每一条路径代表一个决策序列。
换句话说,如果问题包含明确的决策概念,并且解是通过一系列决策产生的,那么它就满足决策树模型,通常可以使用回溯来解决。
在此基础上,动态规划问题还有一些判断的“加分项”。
- 问题包含最大(小)或最多(少)等最优化描述。
- 问题的状态能够使用一个列表、多维矩阵或树来表示,并且一个状态与其周围的状态存在递推关系。
相应地,也存在一些“减分项”。
- 问题的目标是找出所有可能的解决方案,而不是找出最优解。
- 问题描述中有明显的排列组合的特征,需要返回具体的多个方案。
如果一个问题满足决策树模型,并具有较为明显的“加分项”,我们就可以假设它是一个动态规划问题,并在求解过程中验证它。
14.3.2 问题求解步骤¶
动态规划的解题流程会因问题的性质和难度而有所不同,但通常遵循以下步骤:描述决策,定义状态,建立 \(dp\) 表,推导状态转移方程,确定边界条件等。
为了更形象地展示解题步骤,我们使用一个经典问题“最小路径和”来举例。
Question
给定一个 \(n \times m\) 的二维网格 grid ,网格中的每个单元格包含一个非负整数,表示该单元格的代价。机器人以左上角单元格为起始点,每次只能向下或者向右移动一步,直至到达右下角单元格。请返回从左上角到右下角的最小路径和。
图 14-10 展示了一个例子,给定网格的最小路径和为 \(13\) 。
图 14-10 最小路径和示例数据
图解 14-10:四乘四网格的最小路径和
在 4×4 代价网格中从左上角只向右或向下走到右下角,绿色最优路径的七格总和为 13。
给定一个 4×4 的非负整数网格 grid,每个单元格的数值代表经过该格所需支付的代价。从左上角起点 [0, 0] 出发,每次只能向右或向下移动一格,直至到达右下角终点 [3, 3],起点和终点的数值均计入路径总和(行列索引从 0 开始)。
左侧展示完整的 4×4 输入网格,并在左上角标注“起点”、右下角标注“终点”;中央向右箭头指向右侧同一个 4×4 网格,其中一条从左上到右下的七格折线路径以绿色高亮,图下方标注“最小路径和为 13,对应最佳方案为 1→2→2→3→2→1→2”。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
右侧绿色最优路径从起点 [0, 0](值为 1)出发,先向下到 [1, 0](值为 2),再向右到 [1, 1](值为 2),接着向下到 [2, 1](值为 3),随后连续两次向右经过 [2, 2](值为 2)和 [2, 3](值为 1),最后向下到达终点 [3, 3](值为 2),沿途代价相加为 1+2+2+3+2+1+2=13。
第一步:思考每轮的决策,定义状态,从而得到 \(dp\) 表
本题的每一轮的决策就是从当前格子向下或向右走一步。设当前格子的行列索引为 \([i, j]\) ,则向下或向右走一步后,索引变为 \([i+1, j]\) 或 \([i, j+1]\) 。因此,状态应包含行索引和列索引两个变量,记为 \([i, j]\) 。
状态 \([i, j]\) 对应的子问题为:从起始点 \([0, 0]\) 走到 \([i, j]\) 的最小路径和,解记为 \(dp[i, j]\) 。
至此,我们就得到了图 14-11 所示的二维 \(dp\) 矩阵,其尺寸与输入网格 \(grid\) 相同。
图 14-11 状态定义与 dp 表
图解 14-11:把网格位置定义为二维 dp 状态
用行列坐标 [i, j] 定义状态,建立同尺寸 4×4 二维 dp 表对应从起点到各格的最小路径和子问题。
输入为 4×4 非负代价网格 grid(行列索引 0 至 3 的完整数值见表),从左上角起点 [0, 0] 出发每次只能向右或向下走一格,起点与终点均计入路径和。本图对比原网格 grid 与动态规划表 dp 的状态定义。
首先区分两个 4×4 矩阵的含义:grid[i, j] 仅记录经过单个格子的代价,而 dp[i, j] 记录从左上角起点 [0, 0] 走到格子 [i, j](含首尾两格)的累计最小路径和。例如 grid[1, 1] = 2 只代表该格自身的单格代价,不能直接当作累计路径和 dp[1, 1](后者还包含从起点到达该格的路径代价)。
图中在 grid 旁标出行索引 i、i+1 与列索引 j、j+1,并以当前格 [1, 1](代价 2)演示每轮移动决策:向右走一格列索引加 1,到达 [1, 2](即 [i, j+1]),该格代价为 4;向下走一格行索引加 1,到达 [2, 1](即 [i+1, j]),该格代价为 3。每次移动只改变行或列中的一个坐标,因此用二维行列索引 [i, j] 定义状态。
右侧 dp 表是与 grid 尺寸相同的 4×4 矩阵,行列索引均为 0 至 3,单元格依次记作 dp[0, 0] 至 dp[3, 3],分别对应到达各格的最小路径和子问题。本图只建立状态定义与坐标映射,尚未计算和填写具体路径和数值。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
图底部依次列出四项建模定义:决策是每轮向右或向下走一格;状态是所在格子的行列索引 [i,j];子问题是从左上角 [0,0] 到达 [i,j] 的最小路径和;dp 表是记录所有这些子问题解的二维矩阵。
Note
动态规划和回溯过程可以描述为一个决策序列,而状态由所有决策变量构成。它应当包含描述解题进度的所有变量,其包含了足够的信息,能够用来推导出下一个状态。
每个状态都对应一个子问题,我们会定义一个 \(dp\) 表来存储所有子问题的解,状态的每个独立变量都是 \(dp\) 表的一个维度。从本质上看,\(dp\) 表是状态和子问题的解之间的映射。
第二步:找出最优子结构,进而推导出状态转移方程
对于状态 \([i, j]\) ,它只能从上边格子 \([i-1, j]\) 和左边格子 \([i, j-1]\) 转移而来。因此最优子结构为:到达 \([i, j]\) 的最小路径和由 \([i, j-1]\) 的最小路径和与 \([i-1, j]\) 的最小路径和中较小的那一个决定。
根据以上分析,可推出图 14-12 所示的状态转移方程:
图 14-12 最优子结构与状态转移方程
图解 14-12:最小路径和的状态转移
到达内部格子的最后一步只能来自上方或左方,取两处累计最小路径和的较小值再加当前格代价。
在非负数字网格中,从左上角 [0, 0] 出发,每次只能向右或向下移动一格,沿途所有格子的数值(含起点和终点)累加为路径和。记 dp[i, j] 为从起点到达第 i 行、第 j 列格子的最小路径和,行列索引均从 0 开始;本例的 4×4 输入网格见表。
左图为 4×4 原始代价网格 grid,右图为同尺寸的符号 dp 表,各格仅标出状态名 dp[0, 0] 至 dp[3, 3]。左图将当前格 [2, 2](值为 2)涂成绿色,将其上方相邻格 [1, 2](值为 4)涂成紫色、左方相邻格 [2, 1](值为 3)涂成蓝色;右表用相同颜色高亮对应的 dp[2, 2]、dp[1, 2] 与 dp[2, 1]。
右表中一条向下箭头从 dp[1, 2] 指向 dp[2, 2],一条向右箭头从 dp[2, 1] 指向 dp[2, 2]。图下方写出状态转移方程 dp[i, j] = min(dp[i-1, j], dp[i, j-1]) + grid[i, j];注意方程中的 min 比较的是到达两个前驱格的累计最小路径和,而不是左图原始网格里的单格代价 4 和 3。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
以图中绿色高亮的内部格 i=2、j=2 为例,只能从上方 [1, 2] 向下走一格、或从左方 [2, 1] 向右走一格到达该格,因此状态转移写为 dp[2, 2] = min(dp[1, 2], dp[2, 1]) + grid[2, 2],其中 grid[2, 2]=2。右侧 dp 表在此仅展示符号依赖关系,尚未填入具体累计数值。
Note
根据定义好的 \(dp\) 表,思考原问题和子问题的关系,找出通过子问题的最优解来构造原问题的最优解的方法,即最优子结构。
一旦我们找到了最优子结构,就可以使用它来构建出状态转移方程。
第三步:确定边界条件和状态转移顺序
在本题中,处在首行的状态只能从其左边的状态得来,处在首列的状态只能从其上边的状态得来,因此首行 \(i = 0\) 和首列 \(j = 0\) 是边界条件。
如图 14-13 所示,由于每个格子是由其左方格子和上方格子转移而来,因此我们使用循环来遍历矩阵,外循环遍历各行,内循环遍历各列。
图 14-13 边界条件与状态转移顺序
图解 14-13:最小路径和的边界与填表顺序
先设定起点并沿首行向右、首列向下累加初始化边界,再按从上到下、从左到右的正序遍历内部格。
在非负数字网格中从 [0, 0] 出发只能向右或向下移动,起点与终点均计入路径和,dp[i, j] 表示到达第 i 行、第 j 列的最小路径和(行列索引 0 至 3)。本图用左右两个 4×4 符号 dp 表分别说明“边界条件:初始化首行首列”与“状态转移顺序:正序遍历矩阵”,不展示具体网格数值。
左图用绿色标出左上角起点,蓝色标出首行其余格,紫色标出首列其余格;箭头分别沿首行向右、沿首列向下。右图的箭头表示内部格依赖已就绪的上方和左方状态。两表都仅写 dp[0,0] 至 dp[3,3] 等符号。
先初始化起点,再沿唯一到达方向累加首行和首列。内部九格按外层行索引 i = 1、2、3,内层列索引 j = 1、2、3 正序填写。这样,求 dp[i,j] 时,上方 dp[i-1,j] 已在前一行算好,左方 dp[i,j-1] 已在本行左侧算好。下表的计算公式据图中的边界和前驱关系整理,原图没有逐项写出这些公式。
| 区域 | 索引范围 | 前驱 | 计算方式 |
|---|---|---|---|
| 起点 | [0,0] | 无 | dp[0,0]=grid[0,0] |
| 首行 | [0,j],j=1、2、3 | [0,j-1] | dp[0,j]=dp[0,j-1]+grid[0,j] |
| 首列 | [i,0],i=1、2、3 | [i-1,0] | dp[i,0]=dp[i-1,0]+grid[i,0] |
| 内部 | i=1、2、3;各行 j=1、2、3 | [i-1,j] 和 [i,j-1] | dp[i,j]=min(dp[i-1,j],dp[i,j-1])+grid[i,j] |
首行与首列只有一个可用前驱,内部格才需要在上方与左方两个前驱之间取最小值。
Note
边界条件在动态规划中用于初始化 \(dp\) 表,在搜索中用于剪枝。
状态转移顺序的核心是要保证在计算当前问题的解时,所有它依赖的更小子问题的解都已经被正确地计算出来。
根据以上分析,我们已经可以直接写出动态规划代码。然而子问题分解是一种从顶至底的思想,因此按照“暴力搜索 \(\rightarrow\) 记忆化搜索 \(\rightarrow\) 动态规划”的顺序实现更加符合思维习惯。
1. 方法一:暴力搜索¶
从状态 \([i, j]\) 开始搜索,不断分解为更小的状态 \([i-1, j]\) 和 \([i, j-1]\) ,递归函数包括以下要素。
- 递归参数:状态 \([i, j]\) 。
- 返回值:从 \([0, 0]\) 到 \([i, j]\) 的最小路径和 \(dp[i, j]\) 。
- 终止条件:当 \(i = 0\) 且 \(j = 0\) 时,返回代价 \(grid[0, 0]\) 。
- 剪枝:当 \(i < 0\) 时或 \(j < 0\) 时索引越界,此时返回代价 \(+\infty\) ,代表不可行。
实现代码如下:
def min_path_sum_dfs(grid: list[list[int]], i: int, j: int) -> int:
"""最小路径和:暴力搜索"""
# 若为左上角单元格,则终止搜索
if i == 0 and j == 0:
return grid[0][0]
# 若行列索引越界,则返回 +∞ 代价
if i < 0 or j < 0:
return inf
# 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
up = min_path_sum_dfs(grid, i - 1, j)
left = min_path_sum_dfs(grid, i, j - 1)
# 返回从左上角到 (i, j) 的最小路径代价
return min(left, up) + grid[i][j]
/* 最小路径和:暴力搜索 */
int minPathSumDFS(vector<vector<int>> &grid, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return INT_MAX;
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
int up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
return min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}
/* 最小路径和:暴力搜索 */
int minPathSumDFS(int[][] grid, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
int up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
return Math.min(left, up) + grid[i][j];
}
/* 最小路径和:暴力搜索 */
int MinPathSumDFS(int[][] grid, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return int.MaxValue;
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
int up = MinPathSumDFS(grid, i - 1, j);
int left = MinPathSumDFS(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
return Math.Min(left, up) + grid[i][j];
}
/* 最小路径和:暴力搜索 */
func minPathSumDFS(grid [][]int, i, j int) int {
// 若为左上角单元格,则终止搜索
if i == 0 && j == 0 {
return grid[0][0]
}
// 若行列索引越界,则返回 +∞ 代价
if i < 0 || j < 0 {
return math.MaxInt
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
up := minPathSumDFS(grid, i-1, j)
left := minPathSumDFS(grid, i, j-1)
// 返回从左上角到 (i, j) 的最小路径代价
return int(math.Min(float64(left), float64(up))) + grid[i][j]
}
/* 最小路径和:暴力搜索 */
func minPathSumDFS(grid: [[Int]], i: Int, j: Int) -> Int {
// 若为左上角单元格,则终止搜索
if i == 0, j == 0 {
return grid[0][0]
}
// 若行列索引越界,则返回 +∞ 代价
if i < 0 || j < 0 {
return .max
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
let up = minPathSumDFS(grid: grid, i: i - 1, j: j)
let left = minPathSumDFS(grid: grid, i: i, j: j - 1)
// 返回从左上角到 (i, j) 的最小路径代价
return min(left, up) + grid[i][j]
}
/* 最小路径和:暴力搜索 */
function minPathSumDFS(grid, i, j) {
// 若为左上角单元格,则终止搜索
if (i === 0 && j === 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Infinity;
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
const up = minPathSumDFS(grid, i - 1, j);
const left = minPathSumDFS(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
return Math.min(left, up) + grid[i][j];
}
/* 最小路径和:暴力搜索 */
function minPathSumDFS(
grid: Array<Array<number>>,
i: number,
j: number
): number {
// 若为左上角单元格,则终止搜索
if (i === 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Infinity;
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
const up = minPathSumDFS(grid, i - 1, j);
const left = minPathSumDFS(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
return Math.min(left, up) + grid[i][j];
}
/* 最小路径和:暴力搜索 */
int minPathSumDFS(List<List<int>> grid, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
// 在 Dart 中,int 类型是固定范围的整数,不存在表示“无穷大”的值
return BigInt.from(2).pow(31).toInt();
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
int up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
return min(left, up) + grid[i][j];
}
/* 最小路径和:暴力搜索 */
fn min_path_sum_dfs(grid: &Vec<Vec<i32>>, i: i32, j: i32) -> i32 {
// 若为左上角单元格,则终止搜索
if i == 0 && j == 0 {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if i < 0 || j < 0 {
return i32::MAX;
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
let up = min_path_sum_dfs(grid, i - 1, j);
let left = min_path_sum_dfs(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
std::cmp::min(left, up) + grid[i as usize][j as usize]
}
/* 最小路径和:暴力搜索 */
int minPathSumDFS(int grid[MAX_SIZE][MAX_SIZE], int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return INT_MAX;
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
int up = minPathSumDFS(grid, i - 1, j);
int left = minPathSumDFS(grid, i, j - 1);
// 返回从左上角到 (i, j) 的最小路径代价
return myMin(left, up) != INT_MAX ? myMin(left, up) + grid[i][j] : INT_MAX;
}
/* 最小路径和:暴力搜索 */
fun minPathSumDFS(grid: Array<IntArray>, i: Int, j: Int): Int {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0]
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Int.MAX_VALUE
}
// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
val up = minPathSumDFS(grid, i - 1, j)
val left = minPathSumDFS(grid, i, j - 1)
// 返回从左上角到 (i, j) 的最小路径代价
return min(left, up) + grid[i][j]
}
### 最小路径和:暴力搜索 ###
def min_path_sum_dfs(grid, i, j)
# 若为左上角单元格,则终止搜索
return grid[i][j] if i == 0 && j == 0
# 若行列索引越界,则返回 +∞ 代价
return Float::INFINITY if i < 0 || j < 0
# 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
up = min_path_sum_dfs(grid, i - 1, j)
left = min_path_sum_dfs(grid, i, j - 1)
# 返回从左上角到 (i, j) 的最小路径代价
[left, up].min + grid[i][j]
end
可视化运行
图 14-14 给出了以 \(dp[2, 1]\) 为根节点的递归树,其中包含一些重叠子问题,其数量会随着网格 grid 的尺寸变大而急剧增多。
从本质上看,造成重叠子问题的原因为:存在多条路径可以从左上角到达某一单元格。
图 14-14 暴力搜索递归树
图解 14-14:最小路径和的重复递归
从 dp[2,1] 查找前驱时,两条调用路线都到达 dp[1,0],它的子树被展开两次,第二次是重复计算。
在非负数字网格中从 [0, 0] 出发只能向右或向下移动,dp[i, j] 表示到达第 i 行、第 j 列的最小路径和(索引从 0 开始)。本图以 dp[2, 1] 为根节点展示自顶向下的暴力搜索递归树,不给出具体网格权重;注意递归是反向查找“上一行”与“上一列”前驱,方向与实际行走时的向下、向右相反。
有效内部状态取两个前驱返回值的较小值,再加当前格代价:dp[i, j] = min(dp[i-1, j], dp[i, j-1]) + grid[i, j]。起点返回 grid[0, 0],负索引越界时返回正无穷。
递归树的左分支查上一行(路线记“上”),右分支查上一列(路线记“左”);这些路线词表示网格前驱方向,不是树在画面上的左右位置。
从根 dp[2,1] 经 dp[1,1] 再到 dp[1,0],路线是“上→左”;经 dp[2,0] 再到 dp[1,0],路线是“左→上”。这对应右下方的原注“dp[i+1, j] 和 dp[i, j+1] 都依赖 dp[i, j]”:本例中 dp[2,0] 和 dp[1,1] 都依赖 dp[1,0]。
暴力搜索不保存已解状态,所以两次 dp[1,0] 都各自展开子节点 dp[0,0] 与 dp[1,-1]。负索引节点标有“剪枝:索引越界”,按代码返回正无穷,在最小值比较中排除非法前驱。
下方 4×4 符号 dp 表(行、列索引均为 0 至 3)以底色突出本次搜索涉及的六种有效状态:[0,0]、[0,1]、[1,0]、[1,1]、[2,0]、[2,1];其余十格仍标有对应 dp 符号,未参与本次搜索。下表按先进入节点、再查上方、再查左方的调用顺序列出整棵递归树,重复状态用不同路线区分。
| 调用路线 | 状态 | 处理或返回 | 子节点 |
|---|---|---|---|
| 根 | dp[2,1] | 取两前驱较小值,加 grid[2,1] | 上:dp[1,1];左:dp[2,0] |
| 上 | dp[1,1] | 取两前驱较小值,加 grid[1,1] | 上:dp[0,1];左:dp[1,0] |
| 上→上 | dp[0,1] | 取两前驱较小值,加 grid[0,1] | 上:dp[-1,1];左:dp[0,0] |
| 上→上→上 | dp[-1,1] | 越界,返回正无穷 | 不展开 |
| 上→上→左 | dp[0,0] | 起点,返回 grid[0,0] | 不展开 |
| 上→左 | dp[1,0] | 取两前驱较小值,加 grid[1,0] | 上:dp[0,0];左:dp[1,-1] |
| 上→左→上 | dp[0,0] | 起点,返回 grid[0,0] | 不展开 |
| 上→左→左 | dp[1,-1] | 越界,返回正无穷 | 不展开 |
| 左 | dp[2,0] | 取两前驱较小值,加 grid[2,0] | 上:dp[1,0];左:dp[2,-1] |
| 左→上 | dp[1,0] | 取两前驱较小值,加 grid[1,0] | 上:dp[0,0];左:dp[1,-1] |
| 左→上→上 | dp[0,0] | 起点,返回 grid[0,0] | 不展开 |
| 左→上→左 | dp[1,-1] | 越界,返回正无穷 | 不展开 |
| 左→左 | dp[2,-1] | 越界,返回正无穷 | 不展开 |
按表计数,共 13 个调用节点,其中起点 dp[0,0] 出现 3 次,负索引节点出现 4 次:dp[-1,1] 一次、dp[1,-1] 两次、dp[2,-1] 一次。
每个状态都有向下和向右两种选择,从左上角走到右下角总共需要 \(m + n - 2\) 步,所以最差时间复杂度为 \(O(2^{m + n})\) ,其中 \(n\) 和 \(m\) 分别为网格的行数和列数。请注意,这种计算方式未考虑临近网格边界的情况,当到达网格边界时只剩下一种选择,因此实际的路径数量会少一些。
2. 方法二:记忆化搜索¶
我们引入一个和网格 grid 相同尺寸的记忆列表 mem ,用于记录各个子问题的解,并将重叠子问题进行剪枝:
def min_path_sum_dfs_mem(
grid: list[list[int]], mem: list[list[int]], i: int, j: int
) -> int:
"""最小路径和:记忆化搜索"""
# 若为左上角单元格,则终止搜索
if i == 0 and j == 0:
return grid[0][0]
# 若行列索引越界,则返回 +∞ 代价
if i < 0 or j < 0:
return inf
# 若已有记录,则直接返回
if mem[i][j] != -1:
return mem[i][j]
# 左边和上边单元格的最小路径代价
up = min_path_sum_dfs_mem(grid, mem, i - 1, j)
left = min_path_sum_dfs_mem(grid, mem, i, j - 1)
# 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = min(left, up) + grid[i][j]
return mem[i][j]
/* 最小路径和:记忆化搜索 */
int minPathSumDFSMem(vector<vector<int>> &grid, vector<vector<int>> &mem, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return INT_MAX;
}
// 若已有记录,则直接返回
if (mem[i][j] != -1) {
return mem[i][j];
}
// 左边和上边单元格的最小路径代价
int up = minPathSumDFSMem(grid, mem, i - 1, j);
int left = minPathSumDFSMem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
return mem[i][j];
}
/* 最小路径和:记忆化搜索 */
int minPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
// 若已有记录,则直接返回
if (mem[i][j] != -1) {
return mem[i][j];
}
// 左边和上边单元格的最小路径代价
int up = minPathSumDFSMem(grid, mem, i - 1, j);
int left = minPathSumDFSMem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = Math.min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路径和:记忆化搜索 */
int MinPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return int.MaxValue;
}
// 若已有记录,则直接返回
if (mem[i][j] != -1) {
return mem[i][j];
}
// 左边和上边单元格的最小路径代价
int up = MinPathSumDFSMem(grid, mem, i - 1, j);
int left = MinPathSumDFSMem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = Math.Min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路径和:记忆化搜索 */
func minPathSumDFSMem(grid, mem [][]int, i, j int) int {
// 若为左上角单元格,则终止搜索
if i == 0 && j == 0 {
return grid[0][0]
}
// 若行列索引越界,则返回 +∞ 代价
if i < 0 || j < 0 {
return math.MaxInt
}
// 若已有记录,则直接返回
if mem[i][j] != -1 {
return mem[i][j]
}
// 左边和上边单元格的最小路径代价
up := minPathSumDFSMem(grid, mem, i-1, j)
left := minPathSumDFSMem(grid, mem, i, j-1)
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = int(math.Min(float64(left), float64(up))) + grid[i][j]
return mem[i][j]
}
/* 最小路径和:记忆化搜索 */
func minPathSumDFSMem(grid: [[Int]], mem: inout [[Int]], i: Int, j: Int) -> Int {
// 若为左上角单元格,则终止搜索
if i == 0, j == 0 {
return grid[0][0]
}
// 若行列索引越界,则返回 +∞ 代价
if i < 0 || j < 0 {
return .max
}
// 若已有记录,则直接返回
if mem[i][j] != -1 {
return mem[i][j]
}
// 左边和上边单元格的最小路径代价
let up = minPathSumDFSMem(grid: grid, mem: &mem, i: i - 1, j: j)
let left = minPathSumDFSMem(grid: grid, mem: &mem, i: i, j: j - 1)
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = min(left, up) + grid[i][j]
return mem[i][j]
}
/* 最小路径和:记忆化搜索 */
function minPathSumDFSMem(grid, mem, i, j) {
// 若为左上角单元格,则终止搜索
if (i === 0 && j === 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Infinity;
}
// 若已有记录,则直接返回
if (mem[i][j] !== -1) {
return mem[i][j];
}
// 左边和上边单元格的最小路径代价
const up = minPathSumDFSMem(grid, mem, i - 1, j);
const left = minPathSumDFSMem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = Math.min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路径和:记忆化搜索 */
function minPathSumDFSMem(
grid: Array<Array<number>>,
mem: Array<Array<number>>,
i: number,
j: number
): number {
// 若为左上角单元格,则终止搜索
if (i === 0 && j === 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Infinity;
}
// 若已有记录,则直接返回
if (mem[i][j] != -1) {
return mem[i][j];
}
// 左边和上边单元格的最小路径代价
const up = minPathSumDFSMem(grid, mem, i - 1, j);
const left = minPathSumDFSMem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = Math.min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路径和:记忆化搜索 */
int minPathSumDFSMem(List<List<int>> grid, List<List<int>> mem, int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
// 在 Dart 中,int 类型是固定范围的整数,不存在表示“无穷大”的值
return BigInt.from(2).pow(31).toInt();
}
// 若已有记录,则直接返回
if (mem[i][j] != -1) {
return mem[i][j];
}
// 左边和上边单元格的最小路径代价
int up = minPathSumDFSMem(grid, mem, i - 1, j);
int left = minPathSumDFSMem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = min(left, up) + grid[i][j];
return mem[i][j];
}
/* 最小路径和:记忆化搜索 */
fn min_path_sum_dfs_mem(grid: &Vec<Vec<i32>>, mem: &mut Vec<Vec<i32>>, i: i32, j: i32) -> i32 {
// 若为左上角单元格,则终止搜索
if i == 0 && j == 0 {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if i < 0 || j < 0 {
return i32::MAX;
}
// 若已有记录,则直接返回
if mem[i as usize][j as usize] != -1 {
return mem[i as usize][j as usize];
}
// 左边和上边单元格的最小路径代价
let up = min_path_sum_dfs_mem(grid, mem, i - 1, j);
let left = min_path_sum_dfs_mem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i as usize][j as usize] = std::cmp::min(left, up) + grid[i as usize][j as usize];
mem[i as usize][j as usize]
}
/* 最小路径和:记忆化搜索 */
int minPathSumDFSMem(int grid[MAX_SIZE][MAX_SIZE], int mem[MAX_SIZE][MAX_SIZE], int i, int j) {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return INT_MAX;
}
// 若已有记录,则直接返回
if (mem[i][j] != -1) {
return mem[i][j];
}
// 左边和上边单元格的最小路径代价
int up = minPathSumDFSMem(grid, mem, i - 1, j);
int left = minPathSumDFSMem(grid, mem, i, j - 1);
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = myMin(left, up) != INT_MAX ? myMin(left, up) + grid[i][j] : INT_MAX;
return mem[i][j];
}
/* 最小路径和:记忆化搜索 */
fun minPathSumDFSMem(
grid: Array<IntArray>,
mem: Array<IntArray>,
i: Int,
j: Int
): Int {
// 若为左上角单元格,则终止搜索
if (i == 0 && j == 0) {
return grid[0][0]
}
// 若行列索引越界,则返回 +∞ 代价
if (i < 0 || j < 0) {
return Int.MAX_VALUE
}
// 若已有记录,则直接返回
if (mem[i][j] != -1) {
return mem[i][j]
}
// 左边和上边单元格的最小路径代价
val up = minPathSumDFSMem(grid, mem, i - 1, j)
val left = minPathSumDFSMem(grid, mem, i, j - 1)
// 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = min(left, up) + grid[i][j]
return mem[i][j]
}
### 最小路径和:记忆化搜索 ###
def min_path_sum_dfs_mem(grid, mem, i, j)
# 若为左上角单元格,则终止搜索
return grid[0][0] if i == 0 && j == 0
# 若行列索引越界,则返回 +∞ 代价
return Float::INFINITY if i < 0 || j < 0
# 若已有记录,则直接返回
return mem[i][j] if mem[i][j] != -1
# 左边和上边单元格的最小路径代价
up = min_path_sum_dfs_mem(grid, mem, i - 1, j)
left = min_path_sum_dfs_mem(grid, mem, i, j - 1)
# 记录并返回左上角到 (i, j) 的最小路径代价
mem[i][j] = [left, up].min + grid[i][j]
end
可视化运行
如图 14-15 所示,在引入记忆化后,所有子问题的解只需计算一次,因此时间复杂度取决于状态总数,即网格尺寸 \(O(nm)\) 。
图 14-15 记忆化搜索递归树
图解 14-15:最小路径和的记忆化递归
第二次请求 dp[1,0] 时直接读取缓存的有效路径和,不再展开子节点;这与越界返回正无穷的处理不同。
在非负数字网格中从 [0, 0] 出发只能向右或向下移动,dp[i, j] 表示到达第 i 行、第 j 列的最小路径和(索引从 0 开始)。本图同样以 dp[2, 1] 为搜索根,展示引入记忆化缓存 mem 后对重叠子问题的剪枝效果,不展示具体网格权重。递归反向查找上一行与上一列前驱,与实际行走时向下、向右的方向相反。
有效内部状态取两个前驱返回值的较小值,再加当前格代价:dp[i, j] = min(dp[i-1, j], dp[i, j-1]) + grid[i, j]。起点返回 grid[0, 0],负索引越界时返回正无穷。
递归树的左分支查上一行(路线记“上”),右分支查上一列(路线记“左”);这些路线词表示网格前驱方向,不是树在画面上的左右位置。
从根 dp[2,1] 经 dp[1,1] 再到 dp[1,0],路线是“上→左”;经 dp[2,0] 再到 dp[1,0],路线是“左→上”。两条路线请求同一子问题。
先求解 dp[1,1] 分支:首次遇到 dp[1,0] 时,等待两个前驱调用都返回,求出当前格最小路径和并写入 mem[1][0],随后才返回 dp[1,1]。随后求解 dp[2,0] 分支,再次请求 dp[1,0] 时命中“剪枝:已有记录”,直接返回缓存值,不再调用 dp[0,0] 和 dp[1,-1]。dp[2,0] 的另一个子节点 dp[2,-1](路线“左→左”)则是索引越界,返回正无穷;缓存值仍是有效路径和,参与最小值比较。
本次搜索涉及行 0 至 2、列 0 至 1 的六种有效状态:[0,0]、[0,1]、[1,0]、[1,1]、[2,0]、[2,1]。dp[0,1] 和首次求解的 dp[1,0] 各调用一次起点 dp[0,0],对应路线“上→上→左”和“上→左→上”。起点直接返回 grid[0,0],不读写 mem;因此保留两个起点叶节点。下表按先进入节点、再查上方、再查左方的调用顺序列出全部调用;本图没有另画网格或 dp 表。
| 调用路线 | 状态 | 处理或返回 | 子节点 |
|---|---|---|---|
| 根 | dp[2,1] | 取两前驱较小值,加 grid[2,1],计算完成后存入 mem | 上:dp[1,1];左:dp[2,0] |
| 上 | dp[1,1] | 取两前驱较小值,加 grid[1,1],计算完成后存入 mem | 上:dp[0,1];左:dp[1,0] |
| 上→上 | dp[0,1] | 取两前驱较小值,加 grid[0,1],计算完成后存入 mem | 上:dp[-1,1];左:dp[0,0] |
| 上→上→上 | dp[-1,1] | 越界,返回正无穷 | 不展开 |
| 上→上→左 | dp[0,0] | 起点,返回 grid[0,0] | 不展开 |
| 上→左 | dp[1,0] | 取两前驱较小值,加 grid[1,0],计算完成后存入 mem | 上:dp[0,0];左:dp[1,-1] |
| 上→左→上 | dp[0,0] | 起点,返回 grid[0,0] | 不展开 |
| 上→左→左 | dp[1,-1] | 越界,返回正无穷 | 不展开 |
| 左 | dp[2,0] | 取两前驱较小值,加 grid[2,0],计算完成后存入 mem | 上:dp[1,0];左:dp[2,-1] |
| 左→上 | dp[1,0] | 命中缓存,返回已求出的 dp[1,0] | 不展开 |
| 左→左 | dp[2,-1] | 越界,返回正无穷 | 不展开 |
省去第二次 dp[1,0] 的两个子节点后,调用节点从暴力图的 13 个减为 11 个。按表计数,保留 2 个起点 dp[0,0],以及 3 个越界节点 dp[-1,1]、dp[1,-1]、dp[2,-1]。
3. 方法三:动态规划¶
基于迭代实现动态规划解法,代码如下所示:
def min_path_sum_dp(grid: list[list[int]]) -> int:
"""最小路径和:动态规划"""
n, m = len(grid), len(grid[0])
# 初始化 dp 表
dp = [[0] * m for _ in range(n)]
dp[0][0] = grid[0][0]
# 状态转移:首行
for j in range(1, m):
dp[0][j] = dp[0][j - 1] + grid[0][j]
# 状态转移:首列
for i in range(1, n):
dp[i][0] = dp[i - 1][0] + grid[i][0]
# 状态转移:其余行和列
for i in range(1, n):
for j in range(1, m):
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
return dp[n - 1][m - 1]
/* 最小路径和:动态规划 */
int minPathSumDP(vector<vector<int>> &grid) {
int n = grid.size(), m = grid[0].size();
// 初始化 dp 表
vector<vector<int>> dp(n, vector<int>(m));
dp[0][0] = grid[0][0];
// 状态转移:首行
for (int j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移:首列
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 状态转移:其余行和列
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路径和:动态规划 */
int minPathSumDP(int[][] grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
int[][] dp = new int[n][m];
dp[0][0] = grid[0][0];
// 状态转移:首行
for (int j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移:首列
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 状态转移:其余行和列
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路径和:动态规划 */
int MinPathSumDP(int[][] grid) {
int n = grid.Length, m = grid[0].Length;
// 初始化 dp 表
int[,] dp = new int[n, m];
dp[0, 0] = grid[0][0];
// 状态转移:首行
for (int j = 1; j < m; j++) {
dp[0, j] = dp[0, j - 1] + grid[0][j];
}
// 状态转移:首列
for (int i = 1; i < n; i++) {
dp[i, 0] = dp[i - 1, 0] + grid[i][0];
}
// 状态转移:其余行和列
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i, j] = Math.Min(dp[i, j - 1], dp[i - 1, j]) + grid[i][j];
}
}
return dp[n - 1, m - 1];
}
/* 最小路径和:动态规划 */
func minPathSumDP(grid [][]int) int {
n, m := len(grid), len(grid[0])
// 初始化 dp 表
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
dp[0][0] = grid[0][0]
// 状态转移:首行
for j := 1; j < m; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
// 状态转移:首列
for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
// 状态转移:其余行和列
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
dp[i][j] = int(math.Min(float64(dp[i][j-1]), float64(dp[i-1][j]))) + grid[i][j]
}
}
return dp[n-1][m-1]
}
/* 最小路径和:动态规划 */
func minPathSumDP(grid: [[Int]]) -> Int {
let n = grid.count
let m = grid[0].count
// 初始化 dp 表
var dp = Array(repeating: Array(repeating: 0, count: m), count: n)
dp[0][0] = grid[0][0]
// 状态转移:首行
for j in 1 ..< m {
dp[0][j] = dp[0][j - 1] + grid[0][j]
}
// 状态转移:首列
for i in 1 ..< n {
dp[i][0] = dp[i - 1][0] + grid[i][0]
}
// 状态转移:其余行和列
for i in 1 ..< n {
for j in 1 ..< m {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
}
}
return dp[n - 1][m - 1]
}
/* 最小路径和:动态规划 */
function minPathSumDP(grid) {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = Array.from({ length: n }, () =>
Array.from({ length: m }, () => 0)
);
dp[0][0] = grid[0][0];
// 状态转移:首行
for (let j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移:首列
for (let i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 状态转移:其余行和列
for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路径和:动态规划 */
function minPathSumDP(grid: Array<Array<number>>): number {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = Array.from({ length: n }, () =>
Array.from({ length: m }, () => 0)
);
dp[0][0] = grid[0][0];
// 状态转移:首行
for (let j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移:首列
for (let i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 状态转移:其余行和列
for (let i = 1; i < n; i++) {
for (let j: number = 1; j < m; j++) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路径和:动态规划 */
int minPathSumDP(List<List<int>> grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
List<List<int>> dp = List.generate(n, (i) => List.filled(m, 0));
dp[0][0] = grid[0][0];
// 状态转移:首行
for (int j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移:首列
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 状态转移:其余行和列
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
/* 最小路径和:动态规划 */
fn min_path_sum_dp(grid: &Vec<Vec<i32>>) -> i32 {
let (n, m) = (grid.len(), grid[0].len());
// 初始化 dp 表
let mut dp = vec![vec![0; m]; n];
dp[0][0] = grid[0][0];
// 状态转移:首行
for j in 1..m {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移:首列
for i in 1..n {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 状态转移:其余行和列
for i in 1..n {
for j in 1..m {
dp[i][j] = std::cmp::min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
dp[n - 1][m - 1]
}
/* 最小路径和:动态规划 */
int minPathSumDP(int grid[MAX_SIZE][MAX_SIZE], int n, int m) {
// 初始化 dp 表
int **dp = malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
dp[i] = calloc(m, sizeof(int));
}
dp[0][0] = grid[0][0];
// 状态转移:首行
for (int j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移:首列
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 状态转移:其余行和列
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = myMin(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
int res = dp[n - 1][m - 1];
// 释放内存
for (int i = 0; i < n; i++) {
free(dp[i]);
}
return res;
}
/* 最小路径和:动态规划 */
fun minPathSumDP(grid: Array<IntArray>): Int {
val n = grid.size
val m = grid[0].size
// 初始化 dp 表
val dp = Array(n) { IntArray(m) }
dp[0][0] = grid[0][0]
// 状态转移:首行
for (j in 1..<m) {
dp[0][j] = dp[0][j - 1] + grid[0][j]
}
// 状态转移:首列
for (i in 1..<n) {
dp[i][0] = dp[i - 1][0] + grid[i][0]
}
// 状态转移:其余行和列
for (i in 1..<n) {
for (j in 1..<m) {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
}
}
return dp[n - 1][m - 1]
}
### 最小路径和:动态规划 ###
def min_path_sum_dp(grid)
n, m = grid.length, grid.first.length
# 初始化 dp 表
dp = Array.new(n) { Array.new(m, 0) }
dp[0][0] = grid[0][0]
# 状态转移:首行
(1...m).each { |j| dp[0][j] = dp[0][j - 1] + grid[0][j] }
# 状态转移:首列
(1...n).each { |i| dp[i][0] = dp[i - 1][0] + grid[i][0] }
# 状态转移:其余行和列
for i in 1...n
for j in 1...m
dp[i][j] = [dp[i][j - 1], dp[i - 1][j]].min + grid[i][j]
end
end
dp[n -1][m -1]
end
可视化运行
图 14-16 展示了最小路径和的状态转移过程,其遍历了整个网格,因此时间复杂度为 \(O(nm)\) 。
数组 dp 大小为 \(n \times m\) ,因此空间复杂度为 \(O(nm)\) 。
图 14-16 最小路径和的动态规划过程
图解 14-16:最小路径和动态规划
从左上角起点出发,先累计首行与首列的唯一边界路径,再按行逐格取上方与左方较小值加当前格代价,递推至右下角终点。
给定 4×4 非负整数代价网格 grid(行列索引均从 0 开始,完整数值见输入表),要求从左上角起点 [0,0] 走到右下角终点 [3,3],每步只能向右或向下移动一格,路径总代价包含起点与终点的格值。
状态表 dp[i,j] 表示从起点 [0,0] 到达第 i 行第 j 列格子的最小路径和。建表之初填入的 0 仅表示尚未计算的初始占位值,绝不代表存在一条代价为 0 的路径。
边界初始化:起点记为 dp[0,0] = grid[0,0] = 1;第 0 行只能从左方一路向右到达,第 0 列只能从上方一路向下到达,因此先沿首行、首列累加得到共 7 个有效边界格。
内部递推:对第 1 至 3 行、第 1 至 3 列的 9 个内部格,按行从左到右依次计算状态转移方程 dp[i,j] = min(dp[i-1,j], dp[i,j-1]) + grid[i,j],保证每次求值时上方 dp[i-1,j] 与左方 dp[i,j-1] 均已算出有效结果。每帧附带的状态表将格值与“未计算初值”“边界有效”或“已计算”同时写入单元格,便于按坐标直接查阅。
| 行索引 | 列 0 | 列 1 | 列 2 | 列 3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 1 | 5 |
| 1 | 2 | 2 | 4 | 2 |
| 2 | 5 | 3 | 2 | 1 |
| 3 | 4 | 3 | 5 | 2 |
初始化dp存储
建立 4×4 的 dp 状态表并全部填入未计算初值 0;此时包括起点 [0,0]、第 0 行与第 0 列在内的全部 16 格均尚未求值,0 不代表零代价路径。
最小路径和第 1 步:初始化dp存储后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 1 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 2 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 3 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算首行与首列边界
起点 dp[0,0] = grid[0,0] = 1;第 0 行沿唯一向右路径累加得到 [1, 4, 5, 10],第 0 列沿唯一向下路径累加得到 [1, 3, 8, 12]。至此共 7 个边界格成为有效边界值,其余 9 个内部格(行 1 至 3、列 1 至 3)仍为未计算初值 0。
最小路径和第 2 步:计算首行与首列边界后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 2 8,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 3 12,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 计算dp[1,1]
进入内部第 1 行第 1 列:上方前驱 dp[0,1]=4,左方前驱 dp[1,0]=3,取较小值 3 并加上当前格代价 grid[1,1]=2,算得 dp[1,1] = min(4, 3) + 2 = 5。其余 8 个内部格([1,2]、[1,3] 以及行 2 至 3、列 1 至 3)仍为未计算初值 0。
最小路径和第 3 步:计算dp[1,1]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 0,未计算初值 0,未计算初值 2 8,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 3 12,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 计算dp[1,2]
到达 [1,2]:上方前驱 dp[0,2]=5,左方前驱 dp[1,1]=5,两处前驱值相等,任取其一加上当前格代价 grid[1,2]=4,算得 dp[1,2] = min(5, 5) + 4 = 9。其余 7 个内部格([1,3] 以及行 2 至 3、列 1 至 3)仍为未计算初值 0。
最小路径和第 4 步:计算dp[1,2]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 0,未计算初值 2 8,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 3 12,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 计算dp[1,3]
到达第 1 行末格 [1,3]:上方前驱 dp[0,3]=10,左方前驱 dp[1,2]=9,取较小值 9 加上当前格代价 grid[1,3]=2,算得 dp[1,3] = min(10, 9) + 2 = 11。第 1 行已全部有效;行 2 至 3、列 1 至 3 的 6 个内部格仍为未计算初值 0。
最小路径和第 5 步:计算dp[1,3]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 3 12,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 计算dp[2,1]
推进到第 2 行首个内部格 [2,1]:上方前驱 dp[1,1]=5,左方前驱 dp[2,0]=8,取较小值 5 加上当前格代价 grid[2,1]=3,算得 dp[2,1] = min(5, 8) + 3 = 8。剩余 5 个内部格([2,2]、[2,3] 以及第 3 行的列 1 至 3)仍为未计算初值 0。
最小路径和第 6 步:计算dp[2,1]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 8,已计算 0,未计算初值 0,未计算初值 3 12,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 计算dp[2,2]
到达 [2,2]:上方前驱 dp[1,2]=9,左方前驱 dp[2,1]=8,取较小值 8 加上当前格代价 grid[2,2]=2,算得 dp[2,2] = min(9, 8) + 2 = 10。剩余 4 个内部格([2,3]、[3,1]、[3,2]、[3,3])仍为未计算初值 0。
最小路径和第 7 步:计算dp[2,2]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 8,已计算 10,已计算 0,未计算初值 3 12,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 计算dp[2,3]
到达第 2 行末格 [2,3]:上方前驱 dp[1,3]=11,左方前驱 dp[2,2]=10,取较小值 10 加上当前格代价 grid[2,3]=1,算得 dp[2,3] = min(11, 10) + 1 = 11。第 2 行已全部有效;仅剩第 3 行的 [3,1]、[3,2]、[3,3] 为未计算初值 0。
最小路径和第 8 步:计算dp[2,3]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 8,已计算 10,已计算 11,已计算 3 12,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 计算dp[3,1]
推进到最后一行内部格 [3,1]:上方前驱 dp[2,1]=8,左方前驱 dp[3,0]=12,取较小值 8 加上当前格代价 grid[3,1]=3,算得 dp[3,1] = min(8, 12) + 3 = 11。仅剩 [3,2] 和终点 [3,3] 为未计算初值 0。
最小路径和第 9 步:计算dp[3,1]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 8,已计算 10,已计算 11,已计算 3 12,边界有效 11,已计算 0,未计算初值 0,未计算初值 计算dp[3,2]
到达 [3,2]:上方前驱 dp[2,2]=10,左方前驱 dp[3,1]=11,取较小值 10 加上当前格代价 grid[3,2]=5,算得 dp[3,2] = min(10, 11) + 5 = 15。其余 15 格均已有效,仅剩终点 dp[3,3] 为 0(未计算初值)。
最小路径和第 10 步:计算dp[3,2]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 8,已计算 10,已计算 11,已计算 3 12,边界有效 11,已计算 15,已计算 0,未计算初值 计算dp[3,3]
计算最后一个内部格(终点)[3,3]:上方前驱为 dp[2,3]=11,左方前驱为 dp[3,2]=15,取较小值 11 加上当前格代价 grid[3,3]=2,算得 dp[3,3] = min(11, 15) + 2 = 13。至此全表 16 格均已有效。
最小路径和第 11 步:计算dp[3,3]后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 8,已计算 10,已计算 11,已计算 3 12,边界有效 11,已计算 15,已计算 13,已计算 返回最小路径和
全部 16 个状态格已计算完毕,本步不再执行新计算,直接读取并返回右下角终点状态 dp[3,3] = 13 作为最小路径和。本过程只返回最小累计代价,未回溯输出具体路径坐标。
最小路径和第 12 步:返回最小路径和后的 dp 状态 行索引i 列j=0 列j=1 列j=2 列j=3 0 1,边界有效 4,边界有效 5,边界有效 10,边界有效 1 3,边界有效 5,已计算 9,已计算 11,已计算 2 8,边界有效 8,已计算 10,已计算 11,已计算 3 12,边界有效 11,已计算 15,已计算 13,已计算
4. 空间优化¶
由于每个格子只与其左边和上边的格子有关,因此我们可以只用一个单行数组来实现 \(dp\) 表。
请注意,因为数组 dp 只能表示一行的状态,所以我们无法提前初始化首列状态,而是在遍历每行时更新它:
def min_path_sum_dp_comp(grid: list[list[int]]) -> int:
"""最小路径和:空间优化后的动态规划"""
n, m = len(grid), len(grid[0])
# 初始化 dp 表
dp = [0] * m
# 状态转移:首行
dp[0] = grid[0][0]
for j in range(1, m):
dp[j] = dp[j - 1] + grid[0][j]
# 状态转移:其余行
for i in range(1, n):
# 状态转移:首列
dp[0] = dp[0] + grid[i][0]
# 状态转移:其余列
for j in range(1, m):
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
return dp[m - 1]
/* 最小路径和:空间优化后的动态规划 */
int minPathSumDPComp(vector<vector<int>> &grid) {
int n = grid.size(), m = grid[0].size();
// 初始化 dp 表
vector<int> dp(m);
// 状态转移:首行
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for (int i = 1; i < n; i++) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for (int j = 1; j < m; j++) {
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路径和:空间优化后的动态规划 */
int minPathSumDPComp(int[][] grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
int[] dp = new int[m];
// 状态转移:首行
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for (int i = 1; i < n; i++) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for (int j = 1; j < m; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路径和:空间优化后的动态规划 */
int MinPathSumDPComp(int[][] grid) {
int n = grid.Length, m = grid[0].Length;
// 初始化 dp 表
int[] dp = new int[m];
dp[0] = grid[0][0];
// 状态转移:首行
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for (int i = 1; i < n; i++) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for (int j = 1; j < m; j++) {
dp[j] = Math.Min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路径和:空间优化后的动态规划 */
func minPathSumDPComp(grid [][]int) int {
n, m := len(grid), len(grid[0])
// 初始化 dp 表
dp := make([]int, m)
// 状态转移:首行
dp[0] = grid[0][0]
for j := 1; j < m; j++ {
dp[j] = dp[j-1] + grid[0][j]
}
// 状态转移:其余行和列
for i := 1; i < n; i++ {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0]
// 状态转移:其余列
for j := 1; j < m; j++ {
dp[j] = int(math.Min(float64(dp[j-1]), float64(dp[j]))) + grid[i][j]
}
}
return dp[m-1]
}
/* 最小路径和:空间优化后的动态规划 */
func minPathSumDPComp(grid: [[Int]]) -> Int {
let n = grid.count
let m = grid[0].count
// 初始化 dp 表
var dp = Array(repeating: 0, count: m)
// 状态转移:首行
dp[0] = grid[0][0]
for j in 1 ..< m {
dp[j] = dp[j - 1] + grid[0][j]
}
// 状态转移:其余行
for i in 1 ..< n {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0]
// 状态转移:其余列
for j in 1 ..< m {
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
}
}
return dp[m - 1]
}
/* 最小路径和:空间优化后的动态规划 */
function minPathSumDPComp(grid) {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = new Array(m);
// 状态转移:首行
dp[0] = grid[0][0];
for (let j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for (let i = 1; i < n; i++) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for (let j = 1; j < m; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路径和:空间优化后的动态规划 */
function minPathSumDPComp(grid: Array<Array<number>>): number {
const n = grid.length,
m = grid[0].length;
// 初始化 dp 表
const dp = new Array(m);
// 状态转移:首行
dp[0] = grid[0][0];
for (let j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for (let i = 1; i < n; i++) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for (let j = 1; j < m; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路径和:空间优化后的动态规划 */
int minPathSumDPComp(List<List<int>> grid) {
int n = grid.length, m = grid[0].length;
// 初始化 dp 表
List<int> dp = List.filled(m, 0);
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for (int i = 1; i < n; i++) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for (int j = 1; j < m; j++) {
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[m - 1];
}
/* 最小路径和:空间优化后的动态规划 */
fn min_path_sum_dp_comp(grid: &Vec<Vec<i32>>) -> i32 {
let (n, m) = (grid.len(), grid[0].len());
// 初始化 dp 表
let mut dp = vec![0; m];
// 状态转移:首行
dp[0] = grid[0][0];
for j in 1..m {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for i in 1..n {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for j in 1..m {
dp[j] = std::cmp::min(dp[j - 1], dp[j]) + grid[i][j];
}
}
dp[m - 1]
}
/* 最小路径和:空间优化后的动态规划 */
int minPathSumDPComp(int grid[MAX_SIZE][MAX_SIZE], int n, int m) {
// 初始化 dp 表
int *dp = calloc(m, sizeof(int));
// 状态转移:首行
dp[0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
// 状态转移:其余行
for (int i = 1; i < n; i++) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0];
// 状态转移:其余列
for (int j = 1; j < m; j++) {
dp[j] = myMin(dp[j - 1], dp[j]) + grid[i][j];
}
}
int res = dp[m - 1];
// 释放内存
free(dp);
return res;
}
/* 最小路径和:空间优化后的动态规划 */
fun minPathSumDPComp(grid: Array<IntArray>): Int {
val n = grid.size
val m = grid[0].size
// 初始化 dp 表
val dp = IntArray(m)
// 状态转移:首行
dp[0] = grid[0][0]
for (j in 1..<m) {
dp[j] = dp[j - 1] + grid[0][j]
}
// 状态转移:其余行
for (i in 1..<n) {
// 状态转移:首列
dp[0] = dp[0] + grid[i][0]
// 状态转移:其余列
for (j in 1..<m) {
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
}
}
return dp[m - 1]
}
### 最小路径和:空间优化后的动态规划 ###
def min_path_sum_dp_comp(grid)
n, m = grid.length, grid.first.length
# 初始化 dp 表
dp = Array.new(m, 0)
# 状态转移:首行
dp[0] = grid[0][0]
(1...m).each { |j| dp[j] = dp[j - 1] + grid[0][j] }
# 状态转移:其余行
for i in 1...n
# 状态转移:首列
dp[0] = dp[0] + grid[i][0]
# 状态转移:其余列
(1...m).each { |j| dp[j] = [dp[j - 1], dp[j]].min + grid[i][j] }
end
dp[m - 1]
end