Top Down Memoization Java


#1

public class Solution {
static int dp[][];
public int solve(int[][] A) {
int n=A.length,m=A[0].length;
dp=new int[n+1][m+1];
for(int arr[]:dp) Arrays.fill(arr,-1);

    return Math.min(helper(A,0,0),Math.min(helper(A,0,1),helper(A,0,2)));
}

public int helper(int arr[][],int i,int j) {
    if(i>=arr.length) return 0;
    if(i==arr.length-1 ) return dp[i][j]=arr[i][j];
    if(dp[i][j]!=-1) return dp[i][j];
    else { 
        if(j==0) return dp[i][j]=arr[i][j]+Math.min(helper(arr,i+1,j+1),helper(arr,i+1,j+2));
        if(j==1) return dp[i][j]=arr[i][j]+Math.min(helper(arr,i+1,j-1),helper(arr,i+1,j+1));
        else return dp[i][j]=arr[i][j]+Math.min(helper(arr,i+1,j-2),helper(arr,i+1,j-1));
    } 
}

}