Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
class Solution(object): def minPathSum(self, grid): """ :type grid: List[List[int]] :rtype: int """ # 行数 m = len(grid) # 列数 n = len(grid[0]) for i in range(1,n): grid[0][i] += grid[0][i-1] for i in range(1,m): grid[i][0] += grid[i-1][0] for i in range(1,m): for j in range(1,n): grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[-1][-1]
1,3,1 1,4,5 1,4,5 1,4,5 1,4,5 1,4,5 1,4,5
1,5,1 1,5,1 2,5,1 2,7,1 2,7,6 2,7,6 2,7,6
4,2,1 4,2,1 6,2,1 6,2,1 6,2,1 6,8,1 6,8,7
以上为对应的那个数据的变化过程。
原文：https://www.cnblogs.com/jyg694234697/p/9560656.html