不同路径

描述

力扣第 62 题。一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

示例1:

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

示例2:

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

示例3:

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

示例4:

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

提示：

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

思路

本题是动态规划比较好的例子，从起始点到目的地截止点。我们可以想象一下，目标节点的访问路径我们可以从它的上面一个节点访问过来，也可以从它的左边节点访问过来。所以数量是目标节点上一个节点的数量与目标节点的左一个节点的访问数量之和。我们用 f(i,j) 表示访问某个地点的数量函数，则访问 f(i,j) 节点的所有路径用函数表示为：f(i,j) = f(i-1,j) + f(i,j-1)。

我们以示例1 为例子，它是一个三行七列的访问路径。我们可以定义一个二维数组，它上面的值，就表示访问某个位置可以行走的不同路径总和。

我们定义一个访问路径的二维数组：我们用 F(X,Y) 来表示访问的位置。X，Y 表示的是数组的具体索引。

第一行和第一列比较特殊，它没有其它的路径可以访问，只能直达，所以我们可以得到它上面的值都是 1 。所以 F(0,j) 和 以 F(i,0) 这样格式位置的访问路径都是 1。

• 访问第二行第二列，我们可以从从第一行第二列访问过来，也可以从第二行，第一列访问过来，那么我们就会有：F(1,1) = F(0,1) + F(1,0) = 2 种访问路径。

• 访问第二行第三列：我们可以从第二行第二列访问过来，也可以从第一行第三列访问过来，那么我们就会有：F(1,2) = F(0,2) + F(1,1) = 3 种访问路径。

  。。。

• 我们访问第三行第七列的时候，我们可以从第三行第六列访问，也可以从第二行第七列进行访问。则 F(2,6) = F(2,5) + F(1,6) = 28 种访问路径。

因为数组里面，每个里面保存的都是从起始位置访问到该位置的访问数总量，所以求最重节点的访问数量，直接返回数组里面的值即可。

代码具体实现

Java语言版本

class Solution {
    public int uniquePaths(int m, int n) {
        //用来存储每个位置访问路径总数
        int[][] totalRouteArr = new int[m][n];
        //遍历行
        for(int i=0;i<m;i++){
            //遍历列
            for(int j=0;j<n;j++){
                if(i == 0 || j == 0){
                  totalRouteArr[i][j] = 1;
                }else{
                    totalRouteArr[i][j] = (totalRouteArr[i - 1][j]) + (totalRouteArr[i][j-1]);
                }
            }
        }
        return totalRouteArr[m-1][n-1];
    }
}

Go语言版本

func uniquePaths(m int, n int) int {
    //二维用来存储每个位置访问路径总数
    totalRouteArr := make([][]int, m)
	  for i := 0; i < m; i++ {
		    totalRouteArr[i] = make([]int, n)
	  }
    //遍历行
    for i:=0;i<m;i++{
        //遍历列
        for j:=0;j<n;j++{
            if i == 0 || j == 0{
                totalRouteArr[i][j] = 1
            }else {
                totalRouteArr[i][j] = (totalRouteArr[i - 1][j]) + (totalRouteArr[i][j-1])
            }
        }
    }
    return totalRouteArr[m-1][n-1]
}