62. 不同路径 [medium]

https://leetcode-cn.com/problems/unique-paths/

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

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

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

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

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

示例 2:

输入: m = 7, n = 3
输出: 28

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

通过次数127,292 | 提交次数207,317

Second Try

2020-08-02

参考官方题解，这题原来还可以用普通的排列组合来做。想起来了，这是经典的数学题。。

m行n列，从起点到终点总共需要走m - 1 + n - 1步，但是只要什么时候把往下走的m-1步走完，或者把往右走的n-1步走完，剩下的就没有悬念了。因此问题变成了，在 m + n - 2中，选择哪些step来往下走，或者换个提法，往右走？

因此答案是C(m + n - 2)(m - 1)，或者C(m + n - 2)(n - 1).

选择向下走的写法

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        total_steps = m - 1 + n - 1 
        down_steps = m - 1 
        rv = math.factorial(total_steps) / (math.factorial(down_steps) * math.factorial(total_steps - down_steps))
        return int(rv)  # rv为float，还需要转化为int才算通过

执行用时：36 ms, 在所有 Python3 提交中击败了90.20%的用户
内存消耗：13.4 MB, 在所有 Python3 提交中击败了99.42%的用户

选择向右走的写法

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        total_steps = m - 1 + n - 1 
        right_steps = n - 1 
        rv = math.factorial(total_steps) / (math.factorial(right_steps) * math.factorial(total_steps - right_steps))
        return int(rv)  # rv为float，还需要转化为int才算通过

执行用时：28 ms, 在所有 Python3 提交中击败了99.52%的用户
内存消耗：13.6 MB, 在所有 Python3 提交中击败了71.72%的用户

First Try

2020-07-29

有一阵子没写动态规划的题目了，这种类型的题目刚看到总是有点懵逼，只能一点点找迭代的规律。不过这题目没法一下子看到规律，只能先考察普遍性的情况，然后再归纳简化。

考虑用dp[m][n]代表需要走的步数，一次性很难想到规律，不如从额外增加一列或一行的角度来考虑

增加一行：dp[m][n + 1] = dp[m][n] + dp[m-1][n] + dp[m - 2][n] + .. + dp[1][n] 
增加一列：dp[m + 1][n] = dp[m][n] + dp[m][n - 1] + dp[m][n - 2] + ... + dp[m][1]

汇总：

增加一行：dp[m][n + 1] = dp[m][n] + dp[m - 1][n + 1] => dp[m][n] = dp[m][n- 1] + dp[m - 1][n]
增加一列：dp[m + 1][n] = dp[m][n] + dp[m + 1][n - 1] => dp[m][n] = dp[m - 1][n] + dp[m][n - 1]

最后竟然殊途同归，神奇:

dp[m][n] = dp[m][n- 1] + dp[m - 1][n]

额外的起始条件：

dp[1][n] = 1; 
dp[m][1] = 1

update: 写完归纳后，再来看就发现规律很明显了，一眼可以看出来。到达目标点只有两个路径，从左边过来和上面下来，因此只需要考虑左边和上边的点的两种可能性就行了。然后依次内推，直接搞定递推关系，不需要前面一步步的推导。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        """
        考虑用dp[m][n]代表需要走的步数，一次性很难想到规律，不如从额外增加一列或一行的角度来考虑
        增加一行：dp[m][n + 1] = dp[m][n] + dp[m-1][n] + dp[m - 2][n] + .. + dp[1][n] 
        增加一列：dp[m + 1][n] = dp[m][n] + dp[m][n - 1] + dp[m][n - 2] + ... + dp[m][1]

        汇总：
        增加一行：dp[m][n + 1] = dp[m][n] + dp[m - 1][n + 1] => dp[m][n] = dp[m][n- 1] + dp[m - 1][n]
        增加一列：dp[m + 1][n] = dp[m][n] + dp[m + 1][n - 1] => dp[m][n] = dp[m - 1][n] + dp[m][n - 1]

        最后竟然殊途同归，神奇: `dp[m][n] = dp[m][n- 1] + dp[m - 1][n]`. 

        dp[1][n] = 1; dp[m][1] = 1
        """
        
        dp = [[""] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][1] = 1 
        for j in range(n + 1):
            dp[1][j] = 1
        
        def calculate(m, n):
            if dp[m][n] != "":
                return dp[m][n]
            dp[m][n] = calculate(m, n - 1) + calculate(m - 1, n)
            return dp[m][n]
        
        return calculate(m, n)

执行用时：40 ms, 在所有 Python3 提交中击败了74.28%的用户
内存消耗：13.9 MB, 在所有 Python3 提交中击败了6.25%的用户