vvrf / DSA.log

问题拆解

机器人从 m x n 网格的左上角出发，每步只能向右或向下，问走到右下角有多少条不同路径。

按“最后一步”分类：到达格子 (i, j) 的最后一步，要么从上方 (i-1, j) 下来，要么从左方 (i, j-1) 过来，两类不重不漏。于是 f(i, j) = f(i-1, j) + f(i, j-1)，第一行和第一列只有一条路，全是 1。这和爬楼梯是同一个套路，只是递推从一维搬到了二维。

二维表当然能过，但注意转移只用到本行左边和上一行同列，不需要整张表。用一维数组 dp[j] 从左往右刷新：刷新前的 dp[j] 是上一行的值（上方），刚写完的 dp[j-1] 是本行的值（左方），一行行滚下来空间就压到了 O(n)。

一维滚动的正确性全系于遍历方向：从左到右刷新时，dp[j] 的旧值天然扮演“上方”，新值 dp[j-1] 天然扮演“左方”，一次遍历同时用到新旧两代状态。

一维滚动数组

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1); // 第一行全是 1
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1]; // 旧 dp[j] 是上方，dp[j-1] 是左方
        }
    }
    return dp[n - 1];
}

def uniquePaths(m: int, n: int) -> int:
    dp = [1] * n  # 第一行全是 1
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]  # 旧 dp[j] 是上方，dp[j-1] 是左方
    return dp[-1]

func uniquePaths(m int, n int) int {
    dp := make([]int, n)
    for j := range dp { // 第一行全是 1
        dp[j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] += dp[j-1] // 旧 dp[j] 是上方，dp[j-1] 是左方
        }
    }
    return dp[n-1]
}

pub fn unique_paths(m: i32, n: i32) -> i32 {
    let n = n as usize;
    let mut dp = vec![1; n]; // 第一行全是 1
    for _ in 1..m {
        for j in 1..n {
            dp[j] += dp[j - 1]; // 旧 dp[j] 是上方，dp[j-1] 是左方
        }
    }
    dp[n - 1]
}

内层循环从 j = 1 开始：dp[0] 对应第一列，永远是 1，不需要也不能被刷新。如果这道题的转移依赖的是“左上方”而不是“上方”（比如某些编辑距离变体），从左到右滚动就会先把需要的旧值覆盖掉，那时要么倒序遍历、要么额外存一个前值——滚动数组不是无脑压缩，方向必须和依赖关系核对过。

顺带一提，这题有封闭解：一共走 m+n-2 步，其中选 m-1 步向下，答案就是组合数 C(m+n-2, m-1)，可以 O(m) 边乘边除算出来。DP 版的价值在于它能无缝扩展到有障碍物的第 63 题，组合数就不行了。

复杂度

指标	复杂度	原因
时间	`O(mn)`	每个格子转移一次
空间	`O(n)`	一行滚动数组

可以迁移的模式

网格路径计数的通式：当前格 = 各个合法来向之和，边界行列先铺好；
二维 DP 只依赖上一行时，先确认遍历方向不会提前覆盖旧值，再压成一维；
无约束的纯计数问题不妨想想有没有组合数封闭解，但要带约束（障碍、代价）时 DP 更有生命力。

“不同路径”是网格 DP 的最小完整样本：递推、边界、降维三件事都在，后面的最小路径和、障碍物版本都是往这副骨架上加料。