[64] Minimum Path Sum

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

• algorithms
• Medium (43.99%)
• Source Code: 64.minimum-path-sum.py
• Total Accepted: 221.6K
• Total Submissions: 478.4K
• Testcase Example: '[[1,3,1],[1,5,1],[4,2,1]]'

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(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """