Finding the optimal path in a grid

Question

Background I had an interview today and I was asked the following question.

You are given a grid.

  int [][] grid =
                {
                {0,0,0,2,5},
                {0,0,0,1,5},
                {0,1,1,1,1},
                {2,0,0,0,0}
                };

You start from the bottom left off the grid. You can only go up and right. The idea is to get to the TOP right corner. You are to take the path that will get you the most Value.

The output for the above would be 16

My solution

public static int getPathMaxSum(int [][] grid){
    int row = grid.length-1;
    int col = 0;
    int currentSum = grid[row][col];
    return getMax(grid,currentSum,row,col);
}

public static int getMax(int [][] grid,int sum,int row,int col){
    if((isTopRight(grid,row,col)) || (!isValid(grid,row,col))){
        return sum;
    }else{
        sum = sum + grid[row][col];
        return Math.max(getMax(grid,sum,row-1,col),getMax(grid,sum,row,col+1));
    }
}

public static boolean isTopRight(int [][] grid, int row, int col){
    return row == 0 && col == grid[row].length-1;
}

public static boolean isValid(int [][] grid, int row, int col){
    return (row >= 0 &&  row < grid.length) && (col >= 0 && col < grid[row].length);
}

I am trying to solve this recursively. I figure that i have 2 possible choices to make at every position and i want to get the max of the two choices but for some reason I am not able to get the correct output.

I have two helper functions that check if my position is valid meaning inside the grid and also if i have hit the top right and if i have then i hit my base case.

I would love inputs to see where i went wrong.

Answer 1

You don't need a sum parameter in your method.

I assume you already understand how recursion-topdown approach for this problem. But again just for the sake of completeness, the basic formula is:

You start with a cell at row, col get its value and then either you look to UP (row-1, col) or RIGHT (row, col+1).

So the result is going to be:

grid[row][col] + Math.max( getMax( row-1, col, grid ), getMax( row, col+1, grid ) )

Base conditions:

a) If it is top right i.e. the destination, you don't need to recurse you just return the value at that cell.

b) If it is an invalid cell like you have written in your isValid method, you need to return Integer.MIN_VALUE because you could have a negative value in your other cells and you want them to be maximum.

So your getMax function needs to be:

public static int getMax(int [][] grid,int row,int col){
    if (isTopRight(grid,row,col)) {
       return grid[row][col];
    } else if (!isValid(grid,row,col)){
        return Integer.MIN_VALUE;
    } else {
        return grid[row][col] + Math.max(getMax(grid,row-1,col),getMax(grid,row,col+1));
    }
}

You can see working example here