最小路径和
给定一个包含非负整数的 m x n 网格 grid。
请找出一条从左上角到右下角的路径，使得路径上的数字总和最小。
每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1->3->1->1->1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
解法一（二维动态规划）：
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
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] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
};
解法二（一维滚动数组优化）：
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> dp(n, 0);
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] = min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[n - 1];
}
};
核心思想
这题和“不同路径”很像，区别在于这里不是统计路径数量，而是求路径上的最小数字和。
因为每次只能向右或者向下走，所以对于位置 (i, j)，最后一步只可能来自两个位置：
- 从上方
(i - 1, j)向下走一步 - 从左方
(i, j - 1)向右走一步
如果想让到达 (i, j) 的路径和最小，就只需要在这两个来源中选择路径和更小的那个，再加上当前位置的值 grid[i][j]。
这题最关键的观察是：
到达当前位置的最小路径和，只和它上方位置、左方位置的最小路径和有关。
因此可以从左上角开始，按行从左到右计算每个位置的最小路径和。
状态定义
定义：
dp[i][j] 表示从左上角 (0, 0) 走到位置 (i, j) 的最小路径和。
题目要求的答案就是：
dp[m - 1][n - 1]
也就是走到右下角位置的最小路径和。
递推公式推导
考虑位置 (i, j)。
因为只能向右或者向下移动，所以进入 (i, j) 的最后一步只有两种可能。
1. 从上方走下来
如果最后一步来自 (i - 1, j)，那么路径和是：
dp[i - 1][j] + grid[i][j]
2. 从左方走过来
如果最后一步来自 (i, j - 1)，那么路径和是：
dp[i][j - 1] + grid[i][j]
为了让路径和最小，只需要取两者中的较小值：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
代码中写成：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
边界情况
左上角是起点，所以：
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]
如果网格只有一行或一列，上面的初始化也能自然处理。
为什么可以按行递推
计算 dp[i][j] 时，只依赖：
- 上方的
dp[i - 1][j] - 左方的
dp[i][j - 1]
如果从上到下、从左到右遍历：
dp[i - 1][j]已经在上一行算好dp[i][j - 1]已经在当前行左边算好
所以当前位置可以直接由已经计算出的状态推出。
解法二：一维滚动数组优化
二维动态规划中，计算当前行时，只需要用到：
- 上一行同一列的最小路径和
- 当前行左一列的最小路径和
因此可以用一维数组 dp[j] 表示当前处理到这一行时，到达第 j 列的最小路径和。
更新第 i 行第 j 列时：
- 更新前的
dp[j]表示上方位置dp[i - 1][j] - 更新后的
dp[j - 1]表示左方位置dp[i][j - 1]
所以一维写法是：
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
代码中写成：
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
这样可以把空间复杂度从 O(mn) 降到 O(n)。
正确性证明
我们证明：动态规划算法返回的结果等于从左上角到右下角的最小路径和。
结论 1：边界初始化正确
起点 (0, 0) 不需要从其它位置走来，所以到达起点的路径和就是 grid[0][0]。
第一行的每个位置只能从左边走过来，因此它的最小路径和只能由左侧位置累加得到。
第一列的每个位置只能从上边走下来，因此它的最小路径和只能由上方位置累加得到。
所以第一行和第一列的初始化是正确的。
结论 2：递推公式正确计算了每个内部位置的最小路径和
对于内部位置 (i, j)，最后一步只能来自上方 (i - 1, j) 或左方 (i, j - 1)。
如果来自上方，最小路径和是：
dp[i - 1][j] + grid[i][j]
如果来自左方，最小路径和是：
dp[i][j - 1] + grid[i][j]
所有到达 (i, j) 的合法路径都必须属于这两种情况之一，不会遗漏。
为了得到最小路径和，取两者中的较小值即可。
因此：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
正确。
结论 3：按行遍历时，递推所需状态已经计算完成
当计算 dp[i][j] 时，上一行的 dp[i - 1][j] 已经计算完成。
当前行左侧的 dp[i][j - 1] 也已经计算完成。
所以每个状态都能由已知状态正确推出。
结论 4：一维滚动数组与二维动态规划等价
一维数组更新时：
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
其中更新前的 dp[j] 表示二维数组中的 dp[i - 1][j]。
更新后的 dp[j - 1] 表示二维数组中的 dp[i][j - 1]。
这与二维递推公式完全一致。
因此一维滚动数组不会改变计算结果。
得出结论
由结论 1 可知，边界初始化正确。
由结论 2 可知，状态转移正确。
由结论 3 可知，计算顺序正确。
由结论 4 可知，一维优化与二维动态规划等价。
因此算法返回的 dp[m - 1][n - 1] 或 dp[n - 1] 就是从左上角到右下角的最小路径和。
举例理解
以：
grid = [
[1,3,1],
[1,5,1],
[4,2,1]
]
为例。
初始化第一行和第一列后：
1 4 5
2 ? ?
6 ? ?
继续计算内部位置：
dp[1][1] = min(dp[0][1], dp[1][0]) + grid[1][1] = min(4, 2) + 5 = 7dp[1][2] = min(dp[0][2], dp[1][1]) + grid[1][2] = min(5, 7) + 1 = 6dp[2][1] = min(dp[1][1], dp[2][0]) + grid[2][1] = min(7, 6) + 2 = 8dp[2][2] = min(dp[1][2], dp[2][1]) + grid[2][2] = min(6, 8) + 1 = 7
最终 dp 表格是：
1 4 5
2 7 6
6 8 7
所以答案是：
7
对应路径可以是：
1 -> 3 -> 1 -> 1 -> 1
复杂度分析
设网格大小为 m x n。
解法一
需要计算每个位置一次。
- 时间复杂度：
O(mn) - 空间复杂度：
O(mn)
解法二
同样需要计算每个位置一次。
一维数组长度为 n。
- 时间复杂度：
O(mn) - 空间复杂度：
O(n)
解法二空间更优，是更推荐的写法。