IOS 算法(中级篇) ----- 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

exp1

例如
输入：m = 3, n = 7
输出：28

输入：m = 3, n = 2
输出：3

方法1: 动态规划

动态规划其实是比较好理解, 也是相对来说比较好处理此问题方法

举个栗子: 比如要走到 (i, j) 格子, 因为机器人只可以向下或者向右,
固他只能从上方(i - 1, j)下来 或者左方(i, j - 1)向右走过来

我们再看几张图

exp2

(上边界, 左边界只有 1种路线, 因为机器人只能右或下移动)

exp3
exp4
exp5

我们可以直观看到, 如果我们用f(i, j)表示从左上角走到(i, j)的路径数量, 那么可得到动态规划的方程式:

f(i, j) = f(i - 1, j) + f(i, j - 1)

    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        
        var dp = [[Int]](repeating: [Int](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];

    }

其实为了方便些, 我们可以初始建立全为1的dp数组, 固优化上面代码可得

    func uniquePaths(_ m: Int, _ n: Int) -> Int {
    
        var dp = [[Int]](repeating: [Int](repeating: 1, count: n), count: m)

        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 x n 网格, 需要移动 m + n - 2次, 其中 m - 1 次向下移动, n - 1 次向右移动。固从 m + n - 2次移动中选择 m - 1次向下移动方案数, 即

formula

(m!表示 m 的阶乘, 例如 3!=3X2X1, 5!=5X4X3X2X1)

    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        
        var ans = 1, x = n, y = 1
        while y < m {
            ans = ans * x / y
            x += 1
            y += 1
        }

        return ans;
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址