Print entire path of Maximum cost in a maze from first cell to last cell when moving right and bottom is allowed

Question

I need a help in a enhancement to very popular dynamic programming question. Min/Max cost path

Question : There is a 2D matrix which has values (0,1,-1).

0 -> no cherry. can go here
1 ->  cherry present. can go here
-1 -> thorn present. can't go here

we need to print maximum cherrys collected and entire path in which we can collect maximum cherrys.

input : 
{{0, 1, -1}, {1, 0, -1},{1,1,1}};

output : 
4
(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)

I can write the code to print the maximum cherrys collected but not able to get the logic to how to store the entire path. Since we decide which cell to be choosen while backtracking, it appears little tough. didnt find any web help in this regard. I'm stuck, Any help would be appreciated.

public int cherryPickup(int[][] grid) {
    if (grid.length == 0) {
        return -1;
    }
    int[][] dp = new int[grid.length][grid[0].length];
    setDp(dp);
    int forwardMax = getForwardMax(grid, dp, 0, 0);
    return forwardMax;
}

private void setDp(int[][] dp) {
    for (int i = 0; i < dp.length; i++) {
        for (int j = 0; j < dp[0].length; j++) {
            dp[i][j] = -1;
        }
    }
}

private int getForwardMax(int[][] grid, int[][] dp, int i, int j) {
    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    if (grid[i][j] == -1) {
        dp[i][j] = 0;
        return dp[i][j];
    }
    if (i == grid.length - 1 && j == grid[0].length - 1) {
        dp[i][j] = grid[i][j];
        return dp[i][j];
    }
    if (i == grid.length - 1) {
        dp[i][j] = grid[i][j] + getForwardMax(grid, dp, i, j + 1);
        return dp[i][j];
    }
    if (j == grid[0].length - 1) {
        dp[i][j] = grid[i][j] + getForwardMax(grid, dp, i + 1, j);
        return dp[i][j];
    }
    dp[i][j] = grid[i][j] + Math.max(getForwardMax(grid, dp, i + 1, j), getForwardMax(grid, dp, i, j + 1));
    return dp[i][j];

}

As per suggestion in the comment for having the path[][] and storing the index which is maximum. Below code stores (1,1) also 1, which is incorrect.

private int getForwardMax(int[][] grid, int[][] dp, int i, int j, int[][] path) {
    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    if (grid[i][j] == -1) {
        dp[i][j] = 0;
        return dp[i][j];
    }
    if (i == grid.length - 1 && j == grid[0].length - 1) {
        dp[i][j] = grid[i][j];
        return dp[i][j];
    }
    if (i == grid.length - 1) {
        dp[i][j] = grid[i][j] + getForwardMax(grid, dp, i, j + 1, path);
        path[i][j] =1;
        return dp[i][j];
    }
    if (j == grid[0].length - 1) {
        dp[i][j] = grid[i][j] + getForwardMax(grid, dp, i + 1, j, path);
        path[i][j] =1;
        return dp[i][j];
    }
    int left = getForwardMax(grid, dp, i + 1, j, path);
    int right = getForwardMax(grid, dp, i, j + 1, path);
    int max = Math.max(left, right);
    if(max == left) {
        path[i+1][j] = 1;
    } else {
        path[i][j+1] = 1;
    }
    dp[i][j] = grid[i][j] + max;
    return dp[i][j];
}

Answer 1

Ok, bottom up DP is a correct solution as yours. I just realized you won't need separate path[][] to store the path and iterate over them.

You can use a simple while loop and choose the best among the 2 options of right and down. If both happen to have same values, you need not worry as one grid could have multiple correct solutions. So, choosing either one in case of clash will still give you a correct solution.

• We start from (0,0).
• If value contained in dp[x][y+1] cell at the right + current grid[x][y] gives us the value same as dp[x][y], we move right, else we move down.

Snippet:

int x = 0,y = 0;

while(x != rows-1 || y != cols-1){
    System.out.println("( " + x + " , " + y + " )");
    if(x+1 < rows && grid[x][y] + dp[x+1][y] == dp[x][y]){
        x++;
    }else if(y + 1 < cols && grid[x][y] + dp[x][y+1] == dp[x][y]){
        y++;
    }
}

System.out.println("( " + x + " , " + y + " )");

Full Code: https://ideone.com/lRZ6E5

Answer 2

Well if you write your dynamic programming top down (as you did), restoring actual answer is actually very easy.

So you have a function getForwardMax which for given cell, return maximum amount we can collect moving right or down

You also know starting position, so all you need to do is build the answer step by step:

1. Let's say you're in some cell (r,c)
2. if there is only one possible move (you're at border) just do it
3. otherwise we can either move to (r+1,c) or (r,c+1)
4. we also know how much we will earn by moving to those cells and completing our path to the goal from getForwardMax function
5. So we just pick move that gives better result