動機

複習dp

Problem

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 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]Output: 7Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]Output: 12

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

Sol

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        @cache
        def dp(i,j):
            if i == 0 and j == 0:
                return grid[i][j]
            elif i < 0 or i >= len(grid) or j < 0 or j >= len(grid[i]):
                return float('inf')
            else:
                return min(dp(i-1,j),dp(i,j-1))+grid[i][j]
        return dp(len(grid)-1,len(grid[0])-1)