不同路径

🟡 Medium · 🏷️ 数组、动态规划 · LeetCode#62

📖 题目

机器人在 m×n 网格左上角，每次只能向下或向右走一步，求走到右下角一共有多少条不同路径。

💡 思路

爬楼梯的二维版本：一维时 dp[i] = dp[i-1] + dp[i-2]（从前一阶或前两阶来），二维时 dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上方或左方来，走到某格的路径数是"从上面来的路径数"加"从左边来的路径数"）。

第一行和第一列只有一种走法（一路向右，或一路向下），所以初始化全是 1。

💻 代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]   # 第一行/第一列天然是 1
        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[-1][-1]

时间复杂度 O(m × n)，填表填一遍；空间复杂度 O(m × n)，dp 表本身的大小。写递归 f(m-1,n)+f(m,n-1) 思路是对的，但会像爬楼梯的朴素递归一样大量重复计算，超时；填表法自底向上，每个格子只算一次。