64. 最小路径和
题目描述
输入一个 m x n 的网格 grid，每格是一个非负整数。
从左上角走到右下角，每一步只能向右或向下走一格。一条路线的代价是经过的所有格子（含起点和终点）的数字之和。
返回所有路线中最小的代价。
示例 1
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7
解释：沿 1→3→1→1→1 走，总和为 7，是最小值。
示例 2
输入：grid = [[1,2,3],[4,5,6]] 输出：12
解释：沿 1→2→3→6 走，总和为 12。
数据范围
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
解题思路
每格取上方和左方的较小值再加当前权重，并处理第一行第一列边界。
为什么正确
dp[j] 表示处理到当前行时到达该格的最小路径和。
复杂度分析
时间 O(mn)，空间 O(n)。
易错点
第一列只能从上方来，第一行只能从左方来；边界初始化错误会引入不存在的路径。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
dp = [float('inf')] * len(grid[0])
dp[0] = 0
for row in grid:
dp[0] += row[0]
for j in range(1, len(row)):
dp[j] = min(dp[j], dp[j - 1]) + row[j]
return dp[-1]class Solution {
public int minPathSum(int[][] grid) {
int[] dp = new int[grid[0].length];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int[] row : grid) {
dp[0] += row[0];
for (int j = 1; j < row.length; j++)
dp[j] = Math.min(dp[j], dp[j - 1]) + row[j];
}
return dp[dp.length - 1];
}
}class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
vector<int> dp(grid[0].size(), INT_MAX);
dp[0] = 0;
for (auto& row : grid) {
dp[0] += row[0];
for (int j = 1; j < (int)row.size(); j++)
dp[j] = min(dp[j], dp[j - 1]) + row[j];
}
return dp.back();
}
};func minPathSum(grid [][]int) int {
dp := make([]int, len(grid[0]))
for j := range dp {
dp[j] = math.MaxInt32
}
dp[0] = 0
for _, row := range grid {
dp[0] += row[0]
for j := 1; j < len(row); j++ {
dp[j] = min(dp[j], dp[j-1]) + row[j]
}
}
return dp[len(dp)-1]
}var minPathSum = function(grid) {
const dp = new Array(grid[0].length).fill(Infinity);
dp[0] = 0;
for (const row of grid) {
dp[0] += row[0];
for (let j = 1; j < row.length; j++)
dp[j] = Math.min(dp[j], dp[j - 1]) + row[j];
}
return dp[dp.length - 1];
};function minPathSum(grid: number[][]): number {
const dp: number[] = new Array(grid[0].length).fill(Infinity);
dp[0] = 0;
for (const row of grid) {
dp[0] += row[0];
for (let j = 1; j < row.length; j++)
dp[j] = Math.min(dp[j], dp[j - 1]) + row[j];
}
return dp[dp.length - 1];
};