62.不同路径#

一个机器人位于一个m行n列网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？

比如我们有一个2 X 2的网格，其所有路径数就是2，3 X 4的网格路径数是10种

让我们先观察一下，嗯…什么都看不出来 /_ \

没关系，那就让我们用实际实例分析一下

这里我们用S(start)来表示起点，F(finsh)来表示终点，我们一共只有一条路可以走，那就是向右走

1 X 2的也只有一条路可以走

2 X 2的就有两条路可以走了

3X 2有三条路可走

2 X 3有三条路可走

3 X 3有六条路可以走

到了这里我们还是看不出什么，因为我们忽视动态规划里的”动态“了

我们所列的表格都是独立的个体，并没有联系起来，所以让我们联系起来我们之前所有算出的结果

这个表上的数字代表从起点到此点所有可能的路径数，如(2,2)所示数为2，就代表从起点到(2,2)一共有2个路径。对于所有第一行或者第一列的数，我们都视为1，因为其不能向右或向下，所以就只有一条路径

观察这个表格，我们好像观察到了路径数的变化，但不是那么明显，虽然没必要，但是为了明显一点，我把这个表格变大一些

我们发现这个表格竟然对称！

我们发现一个格子的值等于其左边格子和上方格子的和，就比如(4,3)，其值就是左边格子4，与上边格子6的和

所以对于任何一个不在第1行或第1列的格子(i,j)，我们都可以用公式描述其值

1
grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
2
//grid[i - 1][j]代表格子上面的格子的值
3
//grid[i][j - 1]代表格子左边的格子的值

有了这个公式我们就能直接写代码了

1
class Solution {
2
public:
3
    int uniquePaths(int m, int n) {
4
        vector<vector<int>> grid(m,vector<int>(n,1));
5
    //定义一个vector二维数组，(m,vector<int>(n,1))的意思是定义m个列表，每个列表都有n项，且全部初始化为1
6
    //看不懂也可以写int grid[100][100];
7
        for(int i = 1;i < m;i++){
8
            for(int j = 1;j < n;j++){
9
        // 因为第1行、列默认是1，所以不计算
10
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
11
            }
12
        }
13
        return grid[m-1][n-1];
14
    }
15
};
16
//时间复杂O(m x n)遍历m x n次
17
//空间复杂)(m x n)定义m x n个变量

但这题还有一种难以理解的优化方法，不用听懂

对于格子值的计算只用额外依赖与两个值，左边的格子和上面的格子

最左边的格子的值总是1，所以grid[i][1] = gird[i - 1][1] + 1，则gird[i][2] =gird[i - 1][1] + 1 + gird[i - 1][2]，我们发现计算本行的数只需要上一行的数，那么我们只需要一个一维列表，存储上面格子的数，对其更新就行

1
class Solution {
2
public:
3
    int uniquePaths(int m, int n) {
4
        vector<int> x(n,1);
5
        for(int i = 1;i < m;i++){
6
            for(int j = 1;j < n;j++){
7
                x[j] += x[j-1];
8
            }
9
        }
10
        return x[n-1];
11
    }
12
};
13
//时间复杂O(m x n)遍历m x n次
14
//空间复杂)(n)定义n个变量