class Solution:

    def minPathSum(self, grid):
        self.g = grid
        self.DP = {}
        return self.dp(len(grid)-1,len(grid[0])-1)+grid[-1][-1]

    def dp(self,i,j):
        if i==0 and j==0: return 0;
        try:
             return self.DP[(i,j)]
        except KeyError:
            pass
        path1 = 100000
        path2 = 100000
        if i>0:path1 = self.dp(i-1,j)+self.g[i-1][j];
        if j>0:path2 = self.dp(i,j-1)+self.g[i][j-1];
        path = min(path1,path2)
        self.DP[(i,j)] = path
        return path