不同路径

来源Leetcode第62题不同路径

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

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

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

示例 1:

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

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

---

二维动态规划

同第64题，用dp[i][j]表示到第(i,j)位置时有多少种走法
则 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
同时初始化第一行和第一列的的值均为1即可。

代码如下:

public int uniquePaths(int m, int n) {
    int [][] dp = new int[m][n];
    for(int i = 0 ; i < m ; i ++ )
        dp[i][0] = 1;
    for(int i = 0; i < n ; i++)
        dp[0][i] = 1;
    for(int i = 1; i < m ; i ++)
        for(int j = 1 ; j < n ; j++){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    return dp[m - 1][n - 1];
}

一维动态规划

同64题，将列数设置为dp的数组长度，从行开始遍历，则当前位置的步数等于左边的步数 + 上一行同一列位置的步数 即为 dp[j] += dp[j-1] ;

代码如下：

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp,1);
    for (int i = 1; i < m;i++){
        for (int j = 1; j < n; j++){
            dp[j] += dp[j-1] ;
        }
    }
    return dp[n-1];
}

组合数

假设：向右走是1，向下走是2
可行的方案就变成了：112 121 211
到这里是不是就有点儿眼熟了？这不就是一串数字的排列组合问题吗！
m是多少，就有m-1个数字1；n是多少，就有n-1个数字2
所以，我们就用这样的方式，把一个虚假的路径问题转化成了一串只有1和2的数字排列组合问题

即最终解可表示为C(m + n - 2, m - 1)

代码如下：

public int uniquePaths(int m, int n) {
    int N = n + m - 2; 
    int k = m - 1;  
    long res = 1; 
    for (int i = 1; i <= k; i++)
        res = res * (N - k + i) / i;
    return (int) res; 
}