64. Minimum Path Sum

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.

Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]

Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

class Solution:
    def min_path_sum(self, grid):
        m = len(grid)
        n = len(grid[0])
        for i in range(n-1):
            grid[0][i+1] += grid[0][i]
        for j in range(m-1):
            grid[j+1][0] += grid[j][0]
        for i in range(m-1):
            for j in range(n-1):
                grid[i+1][j+1] += (grid[i][j+1] if grid[i][j+1] < grid[i+1][j] else grid[i+1][j])
        return grid[m-1][n-1]


m_n = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
print(Solution().min_path_sum(m_n))

64. Minimum Path Sum

原文：https://www.cnblogs.com/world-0-1/p/13610810.html