62. 不同路径

题意

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

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

“Finish” ）。

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

难度

中等

示例

示例 1：

1669101456132-2c2605bb-b65a-4f09-b104-5a0189e010c1.png

输入：m = 3, n = 7

输出：28

示例 2：

输入：m = 3, n = 2

输出：3

解释：

从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右

3. 向下 -> 向右 -> 向下

示例 4：

输入：m = 7, n = 3

输出：28

示例 5：

输入：m = 3, n = 3

输出：6

分析

我们先用 f[i][j]来表示走到第 i 行第 j 列的方案数，因为无论 m,n 如何变化，只要 i,j 在

m,n 的范围内，f[i][j]无论如何都是相同的。

来观察 n = 1 和 m = 1 的情况，显然，当只有一行或者是只有一列的时候，我们只能往

一个方向走到底，方案只有唯一的一种，那么当 m = 2,n = 2 时，在我们已知 f[1][1]、

f[1][2]和 f[2][1]时，f[2][2]的方案数量，显然是等于 f[1][2]、f[2][1]之和的，因为题目

限制了机器人行走的方向——只能够向下和向右，所以，第二行第二列只能由 第一行第

二列 和 第二行第一列 走到，所以方案数也是这两者之和。

我们再把上面的这个现象推广到一般化，那除了第一行第一列，我们所有的位置都只能由

它的上一列或者是上一行走到，即 f[i][j] = f[i - 1][j] + f[i][j - 1]，于是我们只需要依照

——从上到下，从左到右的顺序依次确定 f[i][j]的值，最后的 f[m][n]即为答案。

实现的时候注意编程语言中的数组是从 0 开始统计的，所以最后答案应该是存储在 f[m -

1][n - 1]上的。

class Solution {

public int uniquePaths(int m, int n) {

int[][] f = new int[m][n];

for(int i = 0;i < m;i++) {

for(int j = 0; j < n; j++) {

if(i == 0 || j == 0){

f[i][j] = 1;

}

else{

f[i][j] = f[i - 1][j] + f[i][j - 1];

}

}

}

return f[m - 1][n - 1];

}

}

1669101467537-d7002eae-742c-424d-ad7f-d477688555cb.png

时间复杂度：$ O(nm) $

空间复杂度：$ O(nm) $

速度看起来不错，但是内存消耗不太理想，原因是我们需要开一个 m * n 大小的二维数组

来记录每个位置的答案，能不能优化一下呢？

能不能直接得出最终的答案，不用一步步的 递推 出 f[m][n]？

回想我们曾经学过的组合数学，机器人其实总共要走的步数不会变化——向右走 n-1 步，

向下走 m-1 步，所以总的步数就是 **n + m - 2** ，那么最终走到第 m 行第 n 列的方案数

就是从 n + m - 2 步中选出 n - 1 步向右走，剩下的自然就是向下走，所以答案即为：

$ C^{n - 1}_{n + m - 2} $

当然也可以理解为从 n + m - 2 步中选出 m - 1 步向下走，那么答案即为

$ C^{m - 1}_{n + m - 2} $

但是这两者的本质是一模一样的，将他们展开便可以发现他们是一样的，只是互为 镜像

的一个关系。

$ C^{n - 1}{n + m - 2} = =C^{m - 1}{n + m - 2} $

所以我们可以写出这样子的代码快速求出答案，并且不用浪费大量的空间来存储中间的各

个过程量。

class Solution {

public int uniquePaths(int m,int n){

long ans = 1;

for(long up = n,down = 1;down < m;down++,up++){

ans = ans * up / down;

}

return (int)ans;

}

}

1669101478384-d7047184-728c-4f13-9d09-0d5146178d87.png

时间复杂度：$ O(m) $

空间复杂度：$ O(1) $

因为我们只使用到了常数个变量，并且只求了一次阶乘，所以非常快速的解决了本题。

总结

本题有两种方法，一种是依靠计算机强大的性能，将每个位置的方案数都计算出来，最终

获得 f[m][n]，第二种则是按照数学方法来推导，直接 一步到位 获得答案，所以计算机其

实无处都隐含着数学，良好的数学基础往往会在一些时候为我们解决问题提供便利。

力扣链接：https://leetcode.cn/problems/unique-paths/