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); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter