64.md

题目地址

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

解答

def minPathSum(grid):
    """
        最小路径和

        输入:
        [
          [1,3,1],
          [1,5,1],
          [4,2,1]
        ]
        输出: 7
        解释: 因为路径 1→3→1→1→1 的总和最小。
    """
    if not grid:
        return 0
    r, c = len(grid[0]), len(grid)

    for i in range(1, r):
        grid[0][i] += grid[0][i - 1]
    for j in range(1, c):
        grid[j][0] += grid[j - 1][0]

    for i in range(1, r):
        for j in range(1, c):
            grid[j][i] += min(grid[j][i - 1], grid[j - 1][i])

    return grid[c - 1][r - 1]