LeetCode 64. 最小路径和

◎

本节目标

用滚动数组维护从左上角到各格的最小累计路径和。

返回网格与路径动态规划框架

查看 LeetCode 原题

题意与约束

从左上到右下只能向右或向下，路径代价是经过格子的数字之和，求最小代价。

第一反应与重复子问题

到达任一格的最后一步只来自上或左。贪心选当前更小数字无法保证后续路径更优。

状态定义与转移推导

dp[r][c] 是到该格的最小路径和：min(dp[r-1][c],dp[r][c-1])+grid[r][c]。一维数组的旧 dp[c] 是上方，更新后的 dp[c-1] 是左方。

正确性依据

任意合法路径按最后一步被完整划分为来自上方或左方两类；选择二者最小前缀再加当前代价即最优子结构。

样例执行过程

[[1,2,100],[3,100,1],[1,1,1]] 不能贪心选 2 后的 100；向下再沿底边得到 7。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<int> dp(cols);
        dp[0] = grid[0][0];
        for (int col = 1; col < cols; col++) {
            dp[col] = dp[col - 1] + grid[0][col];
        }
        for (int row = 1; row < rows; row++) {
            dp[0] += grid[row][0];
            for (int col = 1; col < cols; col++) {
                dp[col] = min(dp[col], dp[col - 1]) + grid[row][col];
            }
        }
        return dp[cols - 1];
    }
};

Python

Python 3

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        dp = [0] * len(grid[0])
        dp[0] = grid[0][0]
        for col in range(1, len(grid[0])):
            dp[col] = dp[col - 1] + grid[0][col]
        for row in range(1, len(grid)):
            dp[0] += grid[row][0]
            for col in range(1, len(grid[0])):
                dp[col] = min(dp[col], dp[col - 1]) + grid[row][col]
        return dp[-1]

复杂度分析

时间 O(rc)，空间 O(c)。

边界与易错点

• 第一行只能从左累计，第一列只能从上累计。
• 单格直接返回自身。
• dp[c] 更新前后分别代表上方、当前行。

模式迁移

障碍物可设为无穷大；最大路径和则把最小值改为最大值，并确认负数初始化。