Q11 Minimum Path Sum - LeetCode 64

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length , n = grid[0].length;

        // return solve(grid , m-1 , n-1 , new Integer[m][n]);

        // tabulization 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++){
                if(i == 0 && j == 0)
                dp[i][j] = grid[0][0];

                else{
                    int up = Integer.MAX_VALUE , left = Integer.MAX_VALUE;
                    //let up and left bring their answers (faith)
                    if(i-1 >= 0)
                    up = grid[i][j] + dp[i-1][j];    

                    if(j-1 >= 0)
                    left = grid[i][j] + dp[i][j-1];

                    //add your value to minimum of both (expectation)
                    dp[i][j] = Math.min(up ,left);
                } 
                
            }
        }
        return dp[m-1][n-1];
    }

    //Recursion -> 2^(m*n) + meoization -> 2*(m*n) Sc- m*n(stack height) + m*n(dp array)
    public int solve(int grid[][] , int r , int c , Integer[][] dp){
        
        if(r == 0 && c == 0)
        return grid[0][0];

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

        int up = Integer.MAX_VALUE , left = Integer.MAX_VALUE;
        //let up and left bring their answers (faith)
        if(r-1 >= 0)
        up = grid[r][c] + solve(grid , r-1 , c , dp);    

        if(c-1 >= 0)
        left = grid[r][c] + solve(grid , r , c-1 , dp);

        //add your value to minimum of both (expectation)
        return dp[r][c] = Math.min(up ,left);
    }
}