Unique Paths (Leetcode 62)

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

Recursion + Memoization

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

Tabulation

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        
        def tabulation(i,j,m,n):
            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]=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]
            
            
        dp=[[0 for i in range(n)] for j in range(m)]
        tabulation(0,0,m,n)
        return dp[0][0]