62_不同路径

类型：数组

• 62. 不同路径 💛

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

  ❓ 一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

  💡 动态规划

  位置 (i, j) 要么是从 (i - 1, j) 过来的，要么是从 (i, j - 1) 过来的。

  转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

  class Solution:
      def uniquePaths(self, m: int, n: int) -> int:
          dp = [[1] * n for _ in range(m)]
          dp[0][0] = 1
          for i in range(m):
              for j in range(n):
                  if i == 0 and j == 0:
                      continue
                  dp[i][j] = (dp[i - 1][j] if i >= 1 else 0) + (dp[i][j - 1] if j >= 1 else 0)
          return dp[-1][-1]

  时间复杂度：O(mn)，空间复杂度：O(mn)