Q12 Maximum Path Sum in the matrix - Coding Ninjas (Striver DP)

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];
	}
}