题目链接 · 灵神原题解（署名来源）

一、寻找子问题

看上图，假设左上角的坐标是 $(0,0)$，右下角的坐标是 $(2,6)$。

想一想，最后一步发生了什么？

• 如果从 $(1,6)$ 向下走到终点 $(2,6)$，那么要解决的问题是从起点 $(0,0)$ 走到 $(1,6)$ 的路径数。
• 如果从 $(2,5)$ 向右走到终点 $(2,6)$，那么要解决的问题是从起点 $(0,0)$ 走到 $(2,5)$ 的路径数。

这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。

二、状态定义与状态转移方程

根据上面的讨论，定义状态为 $\mathit{\text{dfs}}(i,j)$，表示从起点 $(0,0)$ 走到 $(i,j)$ 的路径数。

讨论我们是如何到达 $(i,j)$ 的：

• 如果是从 $(i-1,j)$ 过来，那么问题变成从起点 $(0,0)$ 走到 $(i-1,j)$ 的路径数，即 $\mathit{\text{dfs}}(i-1,j)$。
• 如果是从 $(i,j-1)$ 过来，那么问题变成从起点 $(0,0)$ 走到 $(i,j-1)$ 的路径数，即 $\mathit{\text{dfs}}(i,j-1)$。

这两种情况互斥，根据加法原理，有

$$\mathit{\text{dfs}}(i,j)=\mathit{\text{dfs}}(i-1,j)+\mathit{\text{dfs}}(i,j-1)$$

递归边界：

• $\mathit{\text{dfs}}(-1,j)=\mathit{\text{dfs}}(i,-1)=0$。无法从 $(0,0)$ 到达这些位置。
• $\mathit{\text{dfs}}(0,0)=1$。起点到它自己有一条路径，即原地不动。

递归入口：$\mathit{\text{dfs}}(m-1,n-1)$，这是原问题，也是答案。

三、递归搜索 + 保存递归返回值 = 记忆化搜索

考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

• 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\mathit{\text{memo}}$ 数组中。
• 如果一个状态不是第一次遇到（$\mathit{\text{memo}}$ 中保存的结果不等于 $\mathit{\text{memo}}$ 的初始值），那么可以直接返回 $\mathit{\text{memo}}$ 中保存的结果。

注意：$\mathit{\text{memo}}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\mathit{\text{dfs}}(i,j)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。本题由于方案数不为 $0$，也可以初始化成 $0$。

Python 用户可以无视上面这段，直接用 @cache 装饰器。

具体请看视频讲解 动态规划入门：从记忆化搜索到递推，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

Python 解法1

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（一行代码实现记忆化）
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0:
                return 0
            if i == 0 and j == 0:
                return 1
            return dfs(i - 1, j) + dfs(i, j - 1)
        return dfs(m - 1, n - 1)

C++ 解法1

// C++ 版待补充

Python 解法2

class Solution:
    @cache
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 0 or n == 0:
            return 0
        if m == 1 and n == 1:
            return 1
        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

C++ 解法2

// C++ 版待补充

C++ 解法3

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector memo(m, vector<int>(n));
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0 || j < 0) {
                return 0;
            }
            if (i == 0 && j == 0) {
                return 1;
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res) { // 之前计算过
                return res;
            }
            return res = dfs(i - 1, j) + dfs(i, j - 1);
        };
        return dfs(m - 1, n - 1);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(mn)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(mn)$。
• 空间复杂度：$\mathcal{O}(mn)$。保存多少状态，就需要多少空间。

四、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i+1][j+1]$ 的定义和 $\mathit{\text{dfs}}(i,j)$ 的定义是一样的，都表示从起点 $(0,0)$ 走到 $(i,j)$ 的方案数。这里 $+1$ 是为了把 $\mathit{\text{dfs}}(-1,j)$ 和 $\mathit{\text{dfs}}(i,-1)$ 这些状态也翻译过来，这样我们可以把 $f[0][j]$ 和 $f[i][0]$ 作为初始值。

相应的递推式（状态转移方程）也和 $\mathit{\text{dfs}}$ 一样：

$$f[i+1][j+1]=f[i][j+1]+f[i+1][j]$$

初始值：

• $f[0][j]=f[i][0]=0$，翻译自递归边界 $\mathit{\text{dfs}}(-1,j)=\mathit{\text{dfs}}(i,-1)=0$。
• $f[1][1]=1$，翻译自递归边界 $\mathit{\text{dfs}}(0,0)=1$。

答案为 $f[m][n]$，翻译自递归入口 $\mathit{\text{dfs}}(m-1,n-1)$。

Python 解法4

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                if i == j == 0:
                    f[1][1] = 1
                else:
                    f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j]
        return f[m][n]

C++ 解法4

// C++ 版待补充

C++ 解法5

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

也可以把 $f[0][1]$ 初始化成 $1$，这样我们无需单独计算 $f[1][1]$。从 $\mathit{\text{dfs}}$ 的角度理解，就是把 $(-1,0)$ 当作起点，且第一步只能往下走。

Python 解法6

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][1] = 1
        for i in range(m):
            for j in range(n):
                f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j]
        return f[m][n]

C++ 解法6

// C++ 版待补充

C++ 解法7

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

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$。
• 空间复杂度：$\mathcal{O}(mn)$。

五、空间优化

回顾上面的代码，我们在一行一行地计算 $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]$。

Python 解法8

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [0] * (n + 1)
        f[1] = 1
        for _ in range(m):
            for j in range(n):
                f[j + 1] += f[j]
        return f[n]

C++ 解法8

// C++ 版待补充

C++ 解法9

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];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$。
• 空间复杂度：$\mathcal{O}(n)$。

六、另一种方法：组合数学

再来看示例 1，我们会往下走 $2$ 步，往右走 $6$ 步，一共走 $8$ 步。

比如其中一种走法为

$$\mathrm{右}\mathrm{右}\mathrm{下}\mathrm{右}\mathrm{右}\mathrm{右}\mathrm{下}\mathrm{右}$$

这相当于有 $8$ 个位置，从中选 $2$ 个位置填「下」

$$\underset{―}{\phantom{\mathrm{右}\mathrm{右}}}\mathrm{下}\underset{―}{\phantom{\mathrm{右}\mathrm{右}\mathrm{右}}}\mathrm{下}\underset{―}{\phantom{\mathrm{右}}}$$

确定哪里填「下」，其余位置必然填「右」。

所以只需要计算填「下」的方案数，也就是从 $8$ 个位置选 $2$ 个位置的组合数

$$(\genfrac{}{}{0ex}{}{8}{2})={\displaystyle \frac{8\times 7}{2\times 1}}=28$$

一般地，我们会往下走 $m-1$ 步，往右走 $n-1$ 步，一共走 $m+n-2$ 步。

从 $m+n-2$ 个位置选 $m-1$ 个位置填「下」，组合数为

$$(\genfrac{}{}{0ex}{}{m+n-2}{m-1})={\displaystyle \frac{(m+n-2)!}{(m-1)!(n-1)!}}$$

组合数的计算方法

本题保证答案小于等于 $2\times {10}^9$，可以用简单的循环计算组合数。

组合数的计算公式为

$$(\genfrac{}{}{0ex}{}{n}{i})={\displaystyle \frac{n!}{i!(n-i)!}}$$

把 $i$ 替换成 $i-1$，可得

$$(\genfrac{}{}{0ex}{}{n}{i-1})={\displaystyle \frac{n!}{(i-1)!(n-i+1)!}}$$

对比上面两个等式，可以得到如下递推式

$$(\genfrac{}{}{0ex}{}{n}{i})={\displaystyle \frac{(\genfrac{}{}{0ex}{}{n}{i-1})(n-i+1)}{i}}$$

由于等式左边 ${\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}$ 是整数，所以等式右边的除法一定能整除。

例如

$$(\genfrac{}{}{0ex}{}{9}{4})={\displaystyle \frac{9\times 8\times 7\times 6}{1\times 2\times 3\times 4}}$$

可以先计算 ${\displaystyle \frac{9}{1}}=9$，然后计算 ${\displaystyle \frac{9\times 8}{2}}=36$，然后计算 ${\displaystyle \frac{36\times 7}{3}}=84$，最后计算 ${\displaystyle \frac{84\times 6}{4}}=126$。

注：也可以这样理解，由于任意连续 $i$ 个数中必然有 $i$ 的倍数，所以上述计算过程均为整除，不会产生小数。

所以可以写一个简单的循环，计算

$$(\genfrac{}{}{0ex}{}{n}{k})={\displaystyle \frac{n\times (n-1)\times \cdots \times (n+1-k)}{1\times 2\times \cdots \times k}}$$

如果 $k$ 比较大，可以用组合数恒等式

$$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k})$$

减少循环次数。

Python 解法10

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, m - 1)

C++ 解法10

// C++ 版待补充

Python 解法11

def comb(n: int, k: int) -> int:
    k = min(k, n - k)
    res = 1
    for i in range(1, k + 1):
        res = res * (n + 1 - i) // i
    return res

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, m - 1)

C++ 解法11

// C++ 版待补充

C++ 解法12

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);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(min(m,n))$。
• 空间复杂度：$\mathcal{O}(1)$。

进阶问题

如果网格图中有障碍物，要怎么做？

这题是 63. 不同路径 II。

专题训练

1. 动态规划题单的「二、网格图 DP」。
2. 数学题单的「§2.2 组合计数」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府