LeetCode62.UniquePaths

题目概述

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

题目大意

有个机器人位于表格（m x n）左上角的起点，它每次只能向右或向下移动一格，那么到达右下角的终点，一共有多少条路径？
这里的 m、n 并不是行、列的个数，相反，更类似于横纵坐标

示例

Example1

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example2

Input: m = 7, n = 3
Output: 28

Note

m and n will be at most 100.

解答

思路一：递归

只要没有到达终点，就不停的往右、往下尝试
返回条件是到达终点

var checkEnd = function(position, m, n){//是否达到终点
    if(position.x == m-1 && position.y == n-1){
        return true;
    }else{
        return false;
    }
}
var path = function(position,m, n){//递归
    if(checkEnd(position,m,n)){
        position.total++;
        return;
    }
    if(position.x != m-1){
        position.x++;
        path(position,m,n);
        position.x--;
    }
    if(position.y != n-1){
        position.y++;
        path(position,m,n);
        position.y--;
    }
}
var uniquePaths = function(m, n) {//主函数
    var position = {
        x: 0,
        y: 0,
        total: 0
    }
    path(position,m,n);
    return position.total;
};

不幸的是，并不能通过所有的 case

41/62 test case passed

因为题目不需要知道具体的路径，而只需要最后的路径数量，所以采用递归的当时并不划算

思路二：杨辉三角

可以先了解一下杨辉三角，以及wiki 百科
基于杨辉三角，那么显然！！对，显然，第一行和第一列的路径数都是 1，而任何一个非首行首列的节点都可以通过左侧节点和上侧节点的路径数相加得到达到当前节点的路径数。我们可以利用二维数组来实现：

for(int i = 0; i<m;i++){
        map[i][0] = 1;
    }
    for(int j= 0;j<n;j++){
        map[0][j]=1;
    }
    for(int i = 1;i<m;i++){
        for(int j = 1;j<n;j++){
            map[i][j] = map[i-1][j]+map[i][j-1];
        }
    }

我们可以再对空间进行优化，因为再进行下一次的外围循环时，上一次循环的一维数组已经不再需要了，基于这一点：

var uniquePaths = function(m, n) {
    if(m ==1 || n==1){
        return 1;
    }
    let rtn = [];
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            rtn[j] = (rtn[j] || 1) + (rtn[j-1] || 1);
        }
    }
    return rtn[n-1];
};

Runtime: 44 ms, faster than 99.84% of JavaScript online submissions for Unique Paths.
Memory Usage: 34.1 MB, less than 48.17% of JavaScript online submissions for Unique Paths.

思路三：排列组合

首先，我们一共需要 m+n-2 次移动，其中 m-1 次向下，n-1 次向右。
其次，移动的顺序。每次移动有两种，要么向右、要么向下，因此我们可以运用排列组合的思想。
我们在 m+n-2 中，选择 n-1 次向右，以及 m-1 次向下。

var uniquePaths = function(m, n) {
    let totalPath = n + m - 2;
    let k = m - 1;
    let rtn = 1;
    for (let i = 1; i <= k; i++)
        rtn = rtn * (totalPath - k + i) / i;
    return rtn;
};