Minimum Path Sum (Leetcode 64)

Problem Link: https://leetcode.com/problems/minimum-path-sum/

Recursion + Memoization

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        def recursion(i,j,m,n,grid):
            
            if(i<0 or j<0 or i>=m or j>=n):
                return float('inf')
            
            if(i==m-1 and j==n-1):
                dp[i][j]=grid[i][j]
                return dp[i][j]
            
            if(i+1<m):
                if(dp[i+1][j]!=-1):
                    dp[i+1][j]=recursion(i+1,j,m,n,grid)
                bottom=dp[i+1][j]
            else:
                bottom=float('inf')
            
            if(j+1<n):
                if(dp[i][j+1]!=-1):
                    dp[i][j+1]=recursion(i,j+1,m,n,grid)
                right=dp[i][j+1]
            else:
                right=float('inf')
            
            dp[i][j]=grid[i][j]+min(bottom,right)
            
            return dp[i][j]    
        
        m=len(grid)
        n=len(grid[0])
        dp=[[0 for i in range(n)] for j in range(m)]
        ans=recursion(0,0,m,n,grid)
        return ans

Tabulation

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        m=len(grid)
        n=len(grid[0])
        dp=[[0 for i in range(n)] for j in range(m)]
        for i in range(m-1,-1,-1):
            for j in range(n-1,-1,-1):
                if(i==m-1 and j==n-1):
                    dp[i][j]=grid[i][j]
                elif(i==m-1):
                    dp[i][j]=grid[i][j]+dp[i][j+1]
                elif(j==n-1):
                    dp[i][j]=grid[i][j]+dp[i+1][j]
                else:
                    dp[i][j]=min(dp[i+1][j],dp[i][j+1])+grid[i][j]
        return dp[0][0]