0064. Minimum Path Sum¶
题目信息¶
- 题号:
最小路径和
- 难度:
Medium
- 主题:
动态规划、网格、最小代价、滚动数组
- 原题:
- 重点:
从枚举右下移动序列,推导到只保存到达当前格的最小路径和
题目重述¶
给定一个 m × n 的非负整数网格 grid。从左上角 (0,0) 出发,每一步只能向右或向下移动一格,
直到到达右下角 (m-1,n-1)。
返回所有合法路径中最小的路径和。路径和包含起点、终点以及沿途经过的每一个单元格。
约束为 1 <= m, n <= 200、0 <= grid[row][column] <= 200。
自建示例¶
输入:
[[2,1,4],
[3,2,1],
[5,1,1]]
输出:7
路径 2 -> 1 -> 2 -> 1 -> 1 的和为 7,其他合法路径的和都不小于 7。
输入:[[4],[1],[7]]
输出:12
单列网格只能连续向下,路径和为 4 + 1 + 7。
输入:[[0,0],[0,0]]
输出:0
网格值允许为 0,合法最小路径和也可能为 0。
C++ 实现¶
#include <algorithm>
#include <limits>
#include <vector>
class Solution {
private:
int enumeratePaths(
const std::vector<std::vector<int>>& grid,
int row,
int column
) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
if (row == rows - 1 && column == columns - 1) {
return grid[row][column];
}
int suffix = std::numeric_limits<int>::max();
if (row + 1 < rows) {
suffix = std::min(
suffix,
enumeratePaths(grid, row + 1, column)
);
}
if (column + 1 < columns) {
suffix = std::min(
suffix,
enumeratePaths(grid, row, column + 1)
);
}
return grid[row][column] + suffix;
}
int tableDp(const std::vector<std::vector<int>>& grid) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
std::vector<std::vector<int>> best(
rows,
std::vector<int>(columns, 0)
);
best[0][0] = grid[0][0];
for (int column = 1; column < columns; ++column) {
best[0][column] = best[0][column - 1] + grid[0][column];
}
for (int row = 1; row < rows; ++row) {
best[row][0] = best[row - 1][0] + grid[row][0];
}
for (int row = 1; row < rows; ++row) {
for (int column = 1; column < columns; ++column) {
best[row][column] = grid[row][column] + std::min(
best[row - 1][column],
best[row][column - 1]
);
}
}
return best[rows - 1][columns - 1];
}
int overwriteGrid(std::vector<std::vector<int>>& grid) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
for (int column = 1; column < columns; ++column) {
grid[0][column] += grid[0][column - 1];
}
for (int row = 1; row < rows; ++row) {
grid[row][0] += grid[row - 1][0];
}
for (int row = 1; row < rows; ++row) {
for (int column = 1; column < columns; ++column) {
grid[row][column] += std::min(
grid[row - 1][column],
grid[row][column - 1]
);
}
}
return grid[rows - 1][columns - 1];
}
int rollingDp(const std::vector<std::vector<int>>& grid) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
std::vector<int> best(columns, 0);
best[0] = grid[0][0];
for (int column = 1; column < columns; ++column) {
best[column] = best[column - 1] + grid[0][column];
}
for (int row = 1; row < rows; ++row) {
best[0] += grid[row][0];
for (int column = 1; column < columns; ++column) {
best[column] = grid[row][column] + std::min(
best[column],
best[column - 1]
);
}
}
return best[columns - 1];
}
public:
int minPathSum(std::vector<std::vector<int>>& grid) {
return rollingDp(grid);
}
};
题解¶
路径枚举¶
最直接的方法从起点开始递归。当前位置不是终点时,分别尝试向下和向右;两条分支返回各自后缀路径的最小和, 当前层再加上当前格的数值。
enumeratePaths 完整覆盖所有合法移动序列,因此一定能找到答案。问题在于不同前缀会反复进入同一个格子,
并重新计算从该格到终点的相同后缀。例如先右后下与先下后右都会到达 (1,1)。
网格共有 mn 个位置,而递归树按移动序列展开。消除重复计算的关键,是把状态从“此前走过的整条路径”压缩为
“到达当前格的最小路径和”。
位置最优状态¶
定义:
best[row][column] = 从起点到达 (row,column) 的最小路径和
内部格的最后一步只能来自上方或左方,因此:
best[row][column]
= grid[row][column]
+ min(best[row-1][column], best[row][column-1])
若一条到达当前格的最优路径来自上方,它在上方格之前的前缀也必须最优。否则可以替换为更小的上方前缀, 并保持最后一步不变,从而得到更小的当前路径,与原路径最优矛盾。左方来源同理。
上方与左方覆盖了全部合法最后一步,所以取两者较小值既不会遗漏路径,也不会引入非法路径。
边界累计¶
第一行没有上方来源,只能从左侧连续移动;第一列没有左方来源,只能从上方连续移动。因此边界状态分别为前一个 边界状态加当前格数值:
best[0][column] = best[0][column-1] + grid[0][column]
best[row][0] = best[row-1][0] + grid[row][0]
不能把不存在的来源当成 0。网格值非负,虚构的零代价入口可能小于真实边界路径,使第一行或第一列得到错误结果。
起点状态直接为 grid[0][0],因为路径和包含起点本身。1 × 1 网格也由该初始化直接覆盖。
状态演化¶
对网格:
1 3 1
1 5 1
4 2 1
二维状态依次变为:
1 4 5
2 7 6
6 8 7
例如中心格的状态为 5 + min(4,2) = 7,右下角最终得到最小路径和 7。
原地覆盖¶
二维表中的每个状态只用于右侧和下方转移。若允许修改输入,可以直接把 grid[row][column] 覆盖为到达该格
的最小路径和,转移公式不变。
overwriteGrid 因此只使用常数个循环变量,额外空间为 O(1)。代价是输入矩阵不再保存原始单元格值。
公开入口保持输入不变,所以不选择该方法作为默认实现。
一维滚动¶
处理当前行的 column 位置前:
best[column]仍保存上一行同列状态,即上方最小路径和;best[column-1]已在当前行更新,即左方最小路径和。
因此可以直接执行:
best[column]
= grid[row][column]
+ min(best[column], best[column-1])
更新必须从左向右进行。若从右向左扫描,best[column-1] 尚未更新,表示上一行左侧位置,而不是当前格的左邻居。
第一列在每一行只有上方来源,所以执行 best[0] += grid[row][0]。第一行先做前缀累加,随后所有内部行都能
使用同一条滚动转移。
状态含义¶
每处理完 (row,column),已经更新的当前行前缀都保存精确最小路径和;右侧尚未处理的位置仍保存上一行状态。
这个不变量保证覆盖旧值时,转移所需的上方与左方信息同时存在。
网格值允许为 0,路径和也可能为 0,因此不能用 0 表示未计算状态。二维与滚动方法通过明确的边界初始化区分真实 零值和尚未写入的位置。
方法关系¶
路径枚举保留完整选择树,同一位置的后续问题会被重复计算。二维动态规划把每个位置只计算一次,状态数量降为
mn。
原地方法继续观察到输入格在读取后可以改写,用输入矩阵替代独立状态表。滚动方法则保留输入,只保存上一行与当前行 前缀所需的一维状态。
公开入口调用 rollingDp,在不修改输入的前提下把辅助空间从 O(mn) 降为 O(n)。
复杂度分析¶
设网格有 m 行、n 列。
朴素递归会重复访问相同位置,时间随路径数量指数增长,递归深度为 O(m+n)。
二维动态规划、原地覆盖和滚动数组都恰好处理每个格一次,时间为 O(mn)。二维表使用 O(mn) 辅助空间;
滚动数组使用 O(n) 辅助空间;原地覆盖除输入矩阵外只使用 O(1) 额外空间。