题目描述

一个机器人站在m x n的网格的左上角，它只能向下或向右走，如果它想走到网格的右下角，问有多少种可能的路径

样例

输入: m = 2, n = 2
输出: 2
解释：网格大小为2x2，观察易知机器人共两条路线。

算法1

(dp) $O(n^2)$

dp[i][j] = dp[i][j-1]+dp[i - 1][j]
base case: i == 0 dp[i][j] = dp[i][j - 1]
j == 0 dp[i][j] = dp[i - 1][j]
i==0 && j==0 dp[i][j] = 1;

时间复杂度

time: $O(n^2)$, space:$O(n^2)$

Java 代码

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

算法2

(组合数学) $O(n)$

横向总共会有m - 1步， 纵向也只会有n - 1步，因此用组合数学公式 Combination(m+n-2, m-1)
Combination(N, k) = n! / (k!(n - k)!)
=> C = ( (n - k + 1) * (n - k + 2) * … * n ) / k!

时间复杂度

time:o(n), space: o(1)

Java 代码

public int uniquePaths(int m, int n) {
        int N = m + n - 2;
        int k = m - 1;
        long res = 1;

        for (int i = 1; i <= k; i++) {
            res = res * (N - k + i) / i; 
        }
        return (int)res;
    }