Q-9 Unique Paths - LeetCode 62

class Solution { 
    public int uniquePaths(int m, int n) {
        // return solve(m-1 , n-1 , new Integer[m][n]);
        
        //tabulization 2*m*n    Sc - m*n(dp array)
        int dp[][]= new int[m][n];

        for(int i = 0 ;i < m ; i++){
            for(int j =0 ; j < n ; j++){
                
                //base case
                if(i == 0 && j == 0)
                dp[i][j] = 1;

                else{
                    int down = 0 , right = 0;
    
                    if(i-1 >= 0)
                    down = dp[i-1][j];

                    if(j-1>=0)
                    right = dp[i][j-1];
                    
                    dp[i][j] = (down + right);
                }
            }
        }
        return dp[m-1][n-1];
    }

    //recursion (2^(m*n)) + memoization (2*m*n).    Sc - m*n(stack height) + m*n(dp array)
    /* solving from the point of view of dp[m][n] , so that it is easier to memoize
    that is in how many ways can you reach dp[m][n] from dp[m][n] and moving to (0,0)
    solving smaller problem first
    */
    public int solve(int r , int c , Integer[][] dp){
        if(r == 0 && c == 0 )
        return 1;    

        if(dp[r][c] != null)
        return dp[r][c];

        int down = 0 , right = 0;
        
        if(r-1 >= 0)
        down = solve(r-1,c ,dp);

        if(c-1>=0)
        right = solve(r , c-1 , dp);

        return dp[r][c] = (down + right);
    }
}