LeetCode 62 题讲解

Leetcode 62 题

题干简述

给定：

1. 一个机器人位于一个 m x n 网格的左上角。
2. 机器人每次只能向下或者向右移动一步。

要求：机器人试图达到网格的右下角，请问总共有多少条不同的路径？

题目详情：62. 不同路径

解题思路

现在我们已经刷了好多动态规划的题了，如果你已经理解了动态规划的思想，那么这道题应该非常简单就可以写出来。 （如果想找到之前的动态规划文章，点击👉烤冷面讲算法 - 动态规划

类似「动态规划」LeetCode 70(爬楼梯) 问题，爬楼梯每次只能爬 1 级或者 2 级台阶， 如果我们把目光聚焦于「局部问题」，将第 n 级台阶的爬法记为函数dp，可以推出：dp[n] = dp[n−1] + dp[n−2]

对于本题，机器人每次只能向下或者向右移动一步，相当于原本的一位数组变成了二维数组，写成公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]

假设m=3,n=7，我们可以画出这样一个矩阵：

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1 :
            return 1
        
        dp = [([1] * n) for p in range(m)]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]        

复杂度

时间复杂度O($n^2$)，空间复杂度O($n^2$)。