题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

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

示例 1：

截屏2022-03-18 下午4.37.15.png

输入：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: 动态规划

设dp[i][j]为到达点(i,j)的不同路径数
dp[i][j]的动态转移方程为
dp[i][j] = dp[i-1][j] + dp[i][j-1] (i>=1,j>=1)
边界条件：dp[0][0] = 1
也可以将dp[i][0],dp[j][0] 都作为边界条件，都设为1

// OC
+ (int)uniquePaths1:(int)m n:(int)n {
    int dp[m][n];
    
    for (int i=0; i<m; i++) {
        dp[i][0] = 1;
    }
    
    for (int j=0; j<n; j++) {
        dp[0][j] = 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];
}

// Swift
    static public func uniquePaths1(_ m:Int, _ n:Int) -> Int {
        // dp[i][0] dp[0][j] 都作为边界条件设为1
        if m<1 || n<1 {return 0}
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        for i in 0..<m {
            dp[i][0] = 1
        }
        for j in 0..<n {
            dp[0][j] = 1
        }
        
        for i in 1..<m {
            for j in 1..<n {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
        return dp[m-1][n-1]
    }

思路2:组合数学

从左上角到右下角的过程中，我们需要移动m+n−2 次，其中有m−1 次向下移动，n−1 次向右移动。因此路径的总数，就等于从m+n−2 次移动中选择m−1 次向下移动的方案数，即组合数：
C(m+n-2,m-1) = A(m+n-2,m-1)/A(m-1,m-1) = ((m+n-2)(m+n-3)...n) / ((m-1)(m-2)...1)

// OC
+ (int)uniquePaths2:(int)m n:(int)n {
    int y = 1;
    int x = n;
    int ans = 1;
    while (y<m) {
        ans = (ans * x)/y;
        y++;
        x++;
    }
    return ans;
}

// Swift
    static public func uniquePaths2(_ m:Int, _ n:Int) -> Int {
        if m<1 || n<1 {return 0}
        var x=n
        var y=1
        var ans = 1
        while y<m {
            ans = (ans * x)/y
            y += 1
            x += 1
        }
        return ans
    }

参考：https://leetcode-cn.com/problems/unique-paths
https://leetcode-cn.com/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/