题面

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入： m = 3, n = 7 输出： 28

示例 2：

输入： m = 3, n = 2 输出： 3 解释：从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下

示例 3：

输入： m = 7, n = 3 输出： 28

示例 4：

输入： m = 3, n = 3 输出： 6

提示：

1 <= m, n <= 100 题目数据保证答案小于等于 2 109

分析

代码实现

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp = vector(m, vector(n, 0));
        for (int j = 0; j < n; j++)
            dp[0][j] = 1;
        for (int i = 0; i < m; i++)
            dp[i][0] = 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];
    }
};

空间优化，实际上，dp[i][j] 仅仅依赖于上方和左侧的元素，那么可以压缩为一维 dp
回顾上面的代码，一行一行地计算 $f[i][j]$ ：算完 $f[i]$ ，然后算 $f[i+1]$ ，再算 $f[i+2]$ ；算到 $f[i+2]$ 的时候， $f[i]$ 就再也用不到了
看上去，这里浪费了很多空间，能不能只用一个长为 $n+1$ 的数组呢？好比在一面墙上画画，原来这面墙画的是 $f[i]$ ，现在要画一副新的画，把原来的画覆盖掉，新的画叫做 $f[i+1]$ 。
在这个「覆盖」的过程中，对于这面墙的其中一个点 $f[i+1][j+1]$ ，我们要用 $f[i+1][j+1]$ 覆盖掉 $f[i][j+1]$
怎么覆盖？看转移方程 $f[i+1][j+1] = f[i][j+1] + f[i+1][j]$ 。其中 $f[i][j+1]$ 就地取材， $f[i+1][j]$ 是新画的内容，从这面墙的下标 $j$ 处取到
所以空间优化后是 $f[j+1] = f[j+1] + f[j]$ ，也就是把 $f[j+1]$ 增加 $f[j]$

代码实现

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> f(n + 1);
        f[1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                f[j + 1] += f[j];
            }
        }
        return f[n];
    }
};

实际上，也可以用组合数学来解决，机器人要往下走 m-1 步，往右侧走 n-1 步，这每一步可以选择一种方向，也就是从这些步数中选 m-1 步向下走，即 $C_{m+n-2}^{m-1}$

代码

class Solution {
    long long comb(int n, int k) {
        k = min(k, n - k);
        long long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n + 1 - i) / i;
        }
        return res;
    }

public:
    int uniquePaths(int m, int n) {
        return comb(m + n - 2, m - 1);
    }
};

不同路径 II

如果网格中有障碍物怎么办？显然，第一行的障碍物及其右侧永远无法达到；而第一列的障碍物下方也永远无法达到
同时，有障碍物的位置，其 dp 值一定是 0

代码实现

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp = vector(m, vector(n, 0));
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                for (; j < n; j++)
                    dp[0][j] = 0;
                break;
            } else {
                dp[0][j] = 1;
            }
        }
        for (int j = 0; j < m; j++) {
            if (obstacleGrid[j][0] == 1) {
                for (; j < m; j++)
                    dp[j][0] = 0;
                break;
            } else {
                dp[j][0] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

另外一种方式，递推式中不是减一，而是加一，这样初始化数组时需要空出一行一列，来简化逻辑

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector f(m + 1, vector<int>(n + 1));
        f[0][1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j];
                }
            }
        }
        return f[m][n];
    }
};

空间优化

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid[0].size();
        vector<int> f(n + 1);
        f[1] = 1;
        for (auto& row : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 0) {
                    f[j + 1] += f[j];
                } else {
                    f[j + 1] = 0;
                }
            }
        }
        return f[n];
    }
};

空间优化（原地修改）

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        auto& f = obstacleGrid[0];
        f[0] ^= 1; // 0 变成 1，1 变成 0
        for (int j = 1; j < n; j++) {
            f[j] = f[j] ? 0 : f[j - 1];
        }
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0]) {
                f[0] = 0;
            }
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    f[j] += f[j - 1];
                } else {
                    f[j] = 0;
                }
            }
        }
        return f[n - 1];
    }
};

进阶

如果存在很多个障碍物，且网格规模很大，如何计算？
这是经典的组合数学 + 动态规划 + 容斥原理问题，核心思路如下：
1. 组合数基础：不考虑障碍时，从 (1,1) 到 (x,y) 的路径数为组合数 C ((x-1)+(y-1), x-1)（需要走 (x-1) 步下 + (y-1) 步右，总步数中选 (x-1) 步下）
2. 预处理组合数：由于 h、w 可达 1e5，总步数可达 2e5，需要预处理阶乘和逆元来快速计算组合数
3. 动态规划 + 容斥：
  - 将所有障碍点按行、列升序排序；
  - 定义 dp [i] 为从起点到第 i 个障碍点的合法路径数；
  - dp [i] = 总路径数 (起点到 i) - 所有 j<i 且 j 能到达 i 的障碍点的 dp [j] × 路径数 (j 到 i)；
  - 最终答案 = 总路径数 (起点到终点) - 所有障碍点 i 的 dp [i] × 路径数 (i 到终点)

完整实现

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

typedef long long ll;
const int MAX = 2e5 + 10;  // 最大步数：h+w <= 2e5
const int MOD = 1e9 + 7;
const int MAXN = 2010;     // 障碍点数量上限

// 预处理阶乘、逆元阶乘
ll fact[MAX], inv_fact[MAX];

// 快速幂：计算a^b mod MOD
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和逆元阶乘
void init() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    // 费马小定理求逆元：inv_fact[n] = (n!)^(MOD-2) mod MOD
    inv_fact[MAX-1] = qpow(fact[MAX-1], MOD-2);
    for (int i = MAX-2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

// 计算组合数C(n, k)
ll C(int n, int k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

// 计算从(x1,y1)到(x2,y2)的路径数（只能右下移动）
ll calc(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1;
    int dy = y2 - y1;
    return C(dx + dy, dx);
}

// 障碍点结构体
struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
} obs[MAXN];

ll dp[MAXN];  // dp[i]：从起点到第i个障碍点的合法路径数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    init();  // 预处理组合数
    
    int h, w, n;
    cin >> h >> w >> n;
    for (int i = 0; i < n; i++) {
        cin >> obs[i].x >> obs[i].y;
    }
    
    // 排序障碍点：按行升序，行相同按列升序
    sort(obs, obs + n);
    
    // 计算每个障碍点的dp值
    for (int i = 0; i < n; i++) {
        // 起点(1,1)到obs[i]的总路径数
        dp[i] = calc(1, 1, obs[i].x, obs[i].y);
        // 减去经过前面障碍点的非法路径
        for (int j = 0; j < i; j++) {
            if (obs[j].x <= obs[i].x && obs[j].y <= obs[i].y) {
                dp[i] = (dp[i] - dp[j] * calc(obs[j].x, obs[j].y, obs[i].x, obs[i].y) % MOD + MOD) % MOD;
            }
        }
    }
    
    // 计算最终答案：总路径数 - 经过任意障碍点的路径数
    ll ans = calc(1, 1, h, w);
    for (int i = 0; i < n; i++) {
        ans = (ans - dp[i] * calc(obs[i].x, obs[i].y, h, w) % MOD + MOD) % MOD;
    }
    
    cout << ans << endl;
    
    return 0;
}

不同路径

题面

分析

不同路径 II

进阶

On this page

页面信息