###### tags: `Leetcode` `medium` `dynamic programming` `python` `Top 100 Liked Questions`

# 64. Minimum Path Sum

## [題目連結:] https://leetcode.com/problems/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.


#### [圖片來源:] https://leetcode.com/problems/minimum-path-sum/

## 解題想法:
兄弟題目: [62. Unique Paths](/PkGJvaCWR0ae78I5zaz_BA)

* 此題要求從左上走到右下(最小路徑權重和)
* dp[i][j]:從(0,0)走到(i,j)之路徑最小權重
* 選左邊or上面小的累加
* dp[i][j]+= min(dp[i-1][j],dp[i][j-1])

邊界:
    1 3 1   =>  1         4           5
    1           2    該格+=min(2,4)
    4           6   

## Python:

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,m):
            grid[i][0]+=grid[i-1][0]
        for j in range(1,n):
            grid[0][j]+=grid[0][j-1]
        #跑dp
        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]


if __name__ == '__main__':
    result = Solution()
    grid = [[1,3,1],[1,5,1],[4,2,1]]
    ans = result.minPathSum(grid)
    print(ans)