vvrf / DSA.log

问题拆解

m × n 的非负整数网格，从左上角走到右下角，每步只能向右或向下，求经过数字总和最小的路径。

路径条数是组合数级别的，逐条枚举不现实。贪心地每步挑相邻较小的格子也不行——眼前的小格子可能把你引进一片大数字区。但“只能向右或向下”这个限制给了 DP 很好的结构：走到格子 (i, j) 的最后一步，要么从上方 (i-1, j) 下来，要么从左方 (i, j-1) 过来，没有第三种可能。

于是定义 dp[i][j] 为走到 (i, j) 的最小路径和，两个来源取较小者，再加上当前格子的值：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

首行只能从左来、首列只能从上来，是天然的边界。

移动方向受限的网格题，先问一句“到达每个格子的前驱有哪些”——前驱集合小而固定，就是标准的网格 DP。

一维滚动数组

按行从上往下、行内从左往右填表时，算 dp[i][j] 只用到本行左边一格和上一行同列一格。这两个值恰好可以挤在同一个一维数组里：外层循环推进到第 i 行时，dp[j] 还没被覆盖前存的是上一行的值（正上方），dp[j-1] 已经被覆盖成本行的值（左方），更新顺序天然对齐，不需要第二个数组。

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    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] 是上一行的值，dp[j-1] 是本行的值
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    return dp[n - 1];
}

def minPathSum(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]  # 首行只能从左来
    for i in range(1, m):
        dp[0] += grid[i][0]  # 首列只能从上来
        for j in range(1, n):
            # 此刻 dp[j] 是上一行的值，dp[j-1] 是本行的值
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
    return dp[n - 1]

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    dp := make([]int, n)
    dp[0] = grid[0][0]
    for j := 1; j < n; j++ {
        dp[j] = dp[j-1] + grid[0][j] // 首行只能从左来
    }
    for i := 1; i < m; i++ {
        dp[0] += grid[i][0] // 首列只能从上来
        for j := 1; j < n; j++ {
            // 此刻 dp[j] 是上一行的值，dp[j-1] 是本行的值
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
        }
    }
    return dp[n-1]
}

pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
    let (m, n) = (grid.len(), grid[0].len());
    let mut dp = vec![0; n];
    dp[0] = grid[0][0];
    for j in 1..n {
        dp[j] = dp[j - 1] + grid[0][j]; // 首行只能从左来
    }
    for i in 1..m {
        dp[0] += grid[i][0]; // 首列只能从上来
        for j in 1..n {
            // 此刻 dp[j] 是上一行的值，dp[j-1] 是本行的值
            dp[j] = dp[j].min(dp[j - 1]) + grid[i][j];
        }
    }
    dp[n - 1]
}

最容易忽略的是每行开头那句 dp[0] += grid[i][0]：首列没有左邻居，必须单独累加，忘了它 dp[0] 会一直停在首行的值上，整张表跟着错。如果不想处理这些边界，也可以把 dp 开成 n + 1 长并用一个大数当哨兵，但对这题而言直接特判首行首列更直观。

顺带说明：能压缩成一维的前提是我们只要“最小和”这个数值。如果题目还要求输出路径本身，就得保留整张二维表（或来源方向）用于回溯，压缩会把还原路径需要的信息丢掉。

复杂度

指标	复杂度	原因
时间	`O(m × n)`	每个格子恰好计算一次
空间	`O(n)`	滚动数组只保留一行

可以迁移的模式

网格 DP 的骨架：dp[i][j] 由固定的几个前驱转移而来，方向限制越死结构越清晰；
转移只依赖上一行时，按“行外层、列内层且从左到右”的顺序更新，一维数组可同时充当新旧两行；
首行首列这类“来源不全”的边界要单独初始化，这是网格 DP 最高频的出错点。

把 min 换成求和就是不同路径（62 题），换成 max 就是最大礼物价值——同一张表，三种问法。