不同路径 图解题解

不同路径这道题在问什么

一个 m 行 n 列的网格，机器人从左上角 (0,0) 出发，每一步只能向右或向下移动一格，问走到右下角 (m-1,n-1) 共有多少条不同的路径。要求的是路径条数而不是最短路——每条合法路径长度其实都一样（恰好右移 n-1 次、下移 m-1 次），区别只在这些移动的先后顺序。m=4、n=5 时答案是 35。

为什么想到用动态规划数路径

直接搜索是可行的起点：从起点出发递归枚举每一步向右还是向下，走到终点计一条。但路径条数随网格尺寸指数级增长，纯递归会把同一个格子的子问题重复算无数遍——走到 (2,2) 的方式有很多种，可从 (2,2) 到终点的路径数只需要算一次。

关键观察是反过来看：由于只能向右或向下，任何一条到达 (i,j) 的路径，最后一步只有两种可能——从正上方 (i-1,j) 下来，或从正左方 (i,j-1) 过来，不存在第三个入口。这两类路径最后一步不同，必然互不重复；而所有路径又必属其一，不会遗漏。于是「到 (i,j) 的路径数 = 到上方的路径数 + 到左方的路径数」，加法原理保证不重不漏，问题被拆成规模更小的同类问题。

dp 数组怎么定义，第一行第一列为什么全是 1

定义 dp[i][j] 为从起点 (0,0) 走到 (i,j) 的不同路径条数，答案就是 dp[m-1][n-1]。边界要先铺好：第一行的格子上方没有格子，只能从左边一路向右走过来，路径只有一条；同理第一列只能一路向下。所以第一行、第一列全部初始化为 1，起点 dp[0][0]=1 也读作「原地不动算一种走法」。

这个初始化是整张表的地基。忘了铺 1、留成 0，后面每一格都是在 0 上做加法，整张表全错——这是本题最常见的错误。

转移方程为什么成立，从哪一格开始填

内部格子套 dp[i][j] = dp[i-1][j] + dp[i][j-1]。它成立的依据就是上面的两入口观察：两个来源的路径集合互斥且完备，条数直接相加。填表顺序按行从上到下、每行从左到右，保证算任何一格时它的上方和左方已经算好。

主循环要从 (1,1) 开始而不是 (0,0)：边界已经填好了，从 (1,1) 起每一格才同时有「上」和「左」可加。以样例收尾验证一下，右下角累加出 dp[3][4]=35，与答案一致。

复杂度多少，空间怎么压到一行

时间复杂度 O(m×n)：每个格子只被计算一次，每次是一次加法。空间 O(m×n) 存整张表；由于每格只依赖上一行同列和本行左邻，可以用一维数组滚动更新 dp[j] += dp[j-1]，空间降到 O(n)。

一个常见的延伸问法：如果网格里有障碍物（LeetCode 63 不同路径 II），框架不变，把障碍格的 dp 直接置 0 表示走不到，其余格照样上加左；若起点本身是障碍，答案直接为 0。

Python

def uniquePaths(m, n):
    dp = [[1]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

C++

int uniquePaths(int m, int n){
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for(int i=1;i<m;i++)
        for(int j=1;j<n;j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];

Java

int uniquePaths(int m, int n){
    int[][] dp = new int[m][n];
    for(int i=0;i<m;i++) dp[i][0] = 1;
    for(int j=0;j<n;j++) dp[0][j] = 1;
    for(int i=1;i<m;i++)
        for(int j=1;j<n;j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];