题目链接：https://leetcode-cn.com/problems/minimum-path-sum/
难度：中等

描述：
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

题解

思路：
因为只能向右或向下移动，所以到达grid[i][j]必须经过grid[i-1][j]或grid[i][j-1]，这样就变成了求到grid[i-1][j]和grid[i][j-1]的最小路径和。
分情况讨论：

  • 当i == 0 and j > 0时，是在网格上边界，因此只能从原点一路向右：r[i][j] = r[i][j-1] + grid[i][j]
  • 当j == 0 and i > 0时，是在网格左边界，因此只能从原点一路向下：r[i][j] = r[i-1][j] + grid[i][j]
  • 当i == 0 and j == 0时，位于原点：r[i][j] = grid[i][j]

  • 其余情况：r[i][j] = min(r[i-1][j], r[i][j-1]) + grid[i][j]

    1. class Solution:
    2.   def minPathSum(self, grid: List[List[int]]) -> int:
    3.       m, n = len(grid), len(grid[0])
    4.       r = [[0] * n for _ in range(m)]
    5.       r[0][0] = grid[0][0]
    7.       for i in range(m):
    8.           for j in range(n):
    9.               if i == 0 and j > 0:
    10.                   r[i][j] = r[i][j-1] + grid[i][j]
    11.               elif j == 0 and i > 0:
    12.                   r[i][j] = r[i-1][j] + grid[i][j]
    13.               elif i > 0 and j > 0:
    14.                   r[i][j] = min(r[i-1][j], r[i][j-1]) + grid[i][j]
    15.               else:
    16.                   continue
    17.       return r[m-1][n-1]