62、Unique Paths

题目
一个机器人站在下标为（1，1）的起点走向下标为（m，n）的终点。机器人只允许往下走和往右走。问一共有多少条独特的路线？

思路一：动态规划
通过递归实现计算。在任何一个方块，一共有两条路径，一条是往下走，一条是往右走，如果任何一条路径能够到达终点，则返回1，否则返回0。

解法一

public class Solution{
    public int uniquePaths(int m, int n) {
        return uniquePaths(1,1,m, n);
    }
    
    public int uniquePaths(int currentRow, int currentColumn, int m, int n){
        if(currentRow==m || currentColumn==n){
            return 1;
        }    
        return uniquePaths(currentRow+1, currentColumn, m ,n ) + uniquePaths(currentRow, currentColumn+1, m, n);
    }
}

思路二：杨辉三角
在Dynamic Programming思路的指引下，我们可以尝试将递归的方法改变为循环的方法来解决。这里就运用到了数学中的杨辉三角。很显然，最左侧一行和最顶侧一行的到达路径数都是1，而任何一个非该行列的节点都可以通过左侧节点和上侧节点的路径数相加得到从起点出发到达自己共有的路径数。我们可以利用二维数组来实现叠加。

解法二

public class Solution{
 public int uniquePath3(int m, int n){
        int[][] map = new int[m][n];
        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];
            }
        }
        return map[m-1][n-1];
    }
}

思路三：排列组合
这里运用的是纯数学的思想。根据题目可知，从起点到终点的总步数是一定的，右行或下行的次数也是一定的。我们只需要确定在总部数中哪些步数右行或是哪些步数下行即可知道其对应的路径。这里运用到排列组合的思想。

解法三

public class Solution{
    public int uniquePaths4(int m, int n){
        int totalPath = m + n - 2;
        int down = m-1;
        int right = n-1;
        if(down == 0 || right==0){
            return 1;
        }
        int count = Math.min(down, right);
        long result = 1;
        for(int i = 1 ; i<=count ; i++){
            result *= totalPath--;
            result /= i;
        }
        return (int) result;
    }
}