62.不同路径

发表于： 分类于：
字数： 851 阅读：≈ 2分钟

😄62.不同路径

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

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

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

思路

基本思想

机器人只能向右下角走，只能向右或者向下走，到达某一网格的方式由其上方和左方的网格决定，也就是f(m,n)=f(m-1,n)+f(m,n-1)，其中f(m-1,n)代表左方的网格，f(m,n-1)代表上方的网格

所以只需要从头开始遍历，统计每一个到达每一个网格的路径数，当最终统计到finish时，就可以返回答案

主要是理解递归公式，并且需要初始化，

执行流程

  1. 初始化一个二维vector，二维vector中的每一个元素都是一个一维vector，所以初始化的语句为：
1
2

//res中一共有m个匿名对象，每个匿名对象都是一个vector，初始化了n个0
vector<vector<int>> res( m, vector<int>(n, 0));//初始化的方式

学会这种初始化的方式

  1. 将第一行和第一列的路径数都初始化为1，因为他们要么只能向右，要么只能向下
  2. 从第二行第二列的网格开始进行统计，利用递推公式更新，最终返回结果

代码

根据以上分析，得出一下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int uniquePaths(int m, int n) {
        //定义存放路径数的容器
        vector<vector<int>> res( m, vector<int>(n, 0));//初始化的方式
        //初始化第一行和第一列的路径数
        for(int i=0;i<m;++i){//列
            res[i][0]=1;//只能向下
        }
        //左上角网格被初始化了两次，但是没什么影响
        for(int i=0;i<n;++i){//行
            res[0][i]=1;//只能向右
        }
        for(int i=1;i<m;++i){//行
            for(int j=1;j<n;++j){//列
                //res[i-1][j]代表头顶，res[i][j-1]代表左边
                res[i][j]=res[i-1][j]+res[i][j-1];
            }
        }
        return res[m-1][n-1];
    }
};

总结

关键是推导出递推公式和第一行第一列的初始化，处理完之后就可以直接进行统计，暴力的将所有的网格路径数都统计出来，因为到达(M,N)的路径数需要依赖于前面的路径数

最终返回(m,n)的路径数就是最终的结果