心路历程：

第一反应像是一个回溯问题，但是看到题目中要求最值，大概率是一道DP问题。并且这里面的递推关系也很明显。
这里面边界条件可以有多种处理方法。

解法：动态规划

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dxy = [(1,0), (0,1)]
        @cache
        def dp(i, j):
            if i == m-1 and j == n-1: return grid[i][j]
            candicate = []
            for each in dxy:
                nx, ny = i + each[0], j + each[1]
                if 0<= nx <= m-1 and 0 <= ny <= n-1:
                    candicate.append([nx, ny])
            res = []
            for x, y in candicate:
                res.append(dp(x, y))
            return min(res) + grid[i][j]
        return dp(0,0)