import java.util.* ; import java.io.*; public class Solution { public static int getMaxPathSum(int[][] matrix) { int m = matrix.length , n = matrix[0].length; //DP type -> variable start point - variable end point //Recursion + Memo m*(m*n) // int max = Integer.MIN_VALUE; // for(int j = 0 ; j < n ; j++){ //TC - >m*n // max = Math.max(solve(matrix , m-1 , j , new Integer[m][n]), max); // } // return max; //tabulization m*n 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) dp[i][j]= matrix[i][j]; //same logic as recursion else{ int up = dp[i-1][j]; int diagL = j!= 0 ? dp[i-1][j-1] : Integer.MIN_VALUE; int diagR = j!= n-1 ? dp[i-1][j+1] : Integer.MIN_VALUE; dp[i][j] = Math.max(up , Math.max(diagL,diagR)) + matrix[i][j]; } } } //finding ans in the last row int ans = Integer.MIN_VALUE; for(int j = 0 ; j < n ; j++) ans = Math.max(dp[m-1][j] , ans); return ans; } public static int solve(int[][] matrix , int r , int c, Integer[][] dp ){ if( c < 0 || c >= matrix[0].length) return Integer.MIN_VALUE; if(r == 0) return matrix[r][c]; if(dp[r][c] != null) return dp[r][c]; int up = solve(matrix , r-1 , c,dp); int diagL = solve(matrix , r-1 , c-1,dp); int diagR = solve(matrix , r-1 , c+1,dp); return dp[r][c] = Math.max(up , Math.max(diagL ,diagR)) + matrix[r][c]; } }
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