1. # 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 
    2. # 
    3. #  说明：每次只能向下或者向右移动一步。 
    4. # 
    5. #  
    6. # 
    7. #  示例 1： 
    8. # 
    9. #  
    10. # 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
    11. # 输出：7
    12. # 解释：因为路径 1→3→1→1→1 的总和最小。
    13. #  
    14. # 
    15. #  示例 2： 
    16. # 
    17. #  
    18. # 输入：grid = [[1,2,3],[4,5,6]]
    19. # 输出：12
    20. #  
    21. # 
    22. #  
    23. # 
    24. #  提示： 
    25. # 
    26. #  
    27. #  m == grid.length 
    28. #  n == grid[i].length 
    29. #  1 <= m, n <= 200 
    30. #  0 <= grid[i][j] <= 100 
    31. #  
    32. #  Related Topics 数组 动态规划 
    33. #  👍 736 👎 0
    36. # leetcode submit region begin(Prohibit modification and deletion)
    37. class Solution(object):
    38.     def minPathSum(self, grid):
    39.         """
    40.         :type grid: List[List[int]]
    41.         :rtype: int
    42.         """
    43.         if not grid or not grid[0]:
    44.             return 0
    45.         rows, columns = len(grid), len(grid[0])
    46.         for i in range(1, rows):
    47.             grid[i][0] += grid[i - 1][0]
    48.         for i in range(1, columns):
    49.             grid[0][i] += grid[0][i - 1]
    50.         for i in range(1, rows):
    51.             for j in range(1, columns):
    52.                 grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
    53.         return grid[rows - 1][columns - 1]
    56. # leetcode submit region end(Prohibit modification and deletion)
    58. print(Solution().minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))