Unique Paths II (Leetcode 63)

Problem Link: https://leetcode.com/problems/unique-paths-ii/

Recursion + Memoization

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        
        
        def recursion(obstacleGrid,i,j,m,n):
            
            if(i<0 or j<0 or i>=m or j>=n):
                return 0
            
            if(i==m-1 and j==n-1):
                if(obstacleGrid[i][j]!=1):
                    dp[i][j]=1
                    return 1
                else:
                    return 0
            
            if(obstacleGrid[i][j]==1):
                dp[i][j]=0
                return 0
            
            if(i+1<m):
                if(dp[i+1][j]==-1):
                    dp[i+1][j]=recursion(obstacleGrid,i+1,j,m,n)
                right=dp[i+1][j]
            else:
                right=0
            
            if(j+1<n):
                if(dp[i][j+1]==-1):
                    dp[i][j+1]=recursion(obstacleGrid,i,j+1,m,n)
                bottom=dp[i][j+1]
            else:
                bottom=0
            
            dp[i][j]=right+bottom
            return dp[i][j]
        
        m=len(obstacleGrid)
        n=len(obstacleGrid[0])
        dp=[[-1 for i in range(n)] for j in range(m)]
        ans=recursion(obstacleGrid,0,0,m,n)
        # print(dp)
        return ans

Tabulation

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        
        def tabulation(obstacleGrid,i,j,m,n):
            
            for i in range(m-1,-1,-1):
                for j in range(n-1,-1,-1):
                    if(obstacleGrid[i][j]==1):
                        dp[i][j]=0
                    elif(i==m-1 and j==n-1):
                        dp[i][j]=1
                    elif(i==m-1):
                        dp[i][j]=dp[i][j+1]
                    elif(j==n-1):
                        dp[i][j]=dp[i+1][j]
                    else:
                        dp[i][j]=dp[i+1][j]+dp[i][j+1]
            return dp[0][0]
            
        
        m=len(obstacleGrid)
        n=len(obstacleGrid[0])
        dp=[[-1 for i in range(n)] for j in range(m)]
        ans=tabulation(obstacleGrid,0,0,m,n)
        # print(dp)
        return ans