64_最小路径和

类型：数组

• 64. 最小路径和 💛

  https://leetcode-cn.com/problems/minimum-path-sum/

  ❓ 给定一个包含非负整数的 m x n 网格，从左上角出发，每次只能向下或者向右移动一步，请找出一条到右下角的路径，使得路径上的数字总和为最小。

  💡 动态规划

  位置 (i, j) 可以由位置 (i - 1, j) 或 (i, j - 1) 走过来。

  转移方程：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

  class Solution:
      def minPathSum(self, grid: List[List[int]]) -> int:
          if not grid or not grid[0]:
              return 0
  
          rows, columns = len(grid), len(grid[0])
          dp = [[0] * columns for _ in range(rows)]
          dp[0][0] = grid[0][0]
          for i in range(1, rows):
              dp[i][0] = dp[i - 1][0] + grid[i][0]
          for j in range(1, columns):
              dp[0][j] = dp[0][j - 1] + grid[0][j]
          for i in range(1, rows):
              for j in range(1, columns):
                  dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
  
          return dp[rows - 1][columns - 1]

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