Печатать весь путь максимальной стоимости в лабиринте от первой до последней ячейки, если разрешено перемещение вправо и влево

Question

Мне нужна помощь в расширении очень популярного вопроса динамического программирования. Мин. / Макс. Стоимость пути

Вопрос: существует двумерная матрица со значениями (0,1, -1).

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

нам нужно напечатать максимальное количество собранных вишен и весь путь, по которому мы можем собрать максимальное количество вишен.

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

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

Я могу написать код для печатимаксимум вишни собрано, но не в состоянии понять, как хранить весь путь. Так как мы решаем, какую ячейку выбрать при возврате, она кажется немного сложной. не нашел никакой веб-помощи в этом отношении. Я застрял, любая помощь будет оценена.

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

}

В соответствии с предложением в комментарии для указания пути [] [] и хранения индекса, который является максимальным. Ниже кодахранит (1,1) также 1, что неверно.

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

ОК, DP снизу вверх - правильное решение, как и ваше. Я только что понял, что вам не понадобится отдельный path[][] для хранения пути и итерации по ним.

Вы можете использовать простой цикл while и выбрать лучший из двух вариантов: вправо и вниз. Если оба значения имеют одинаковые значения, вам не нужно беспокоиться, поскольку одна сетка может иметь несколько правильных решений. Таким образом, выбор любого из них в случае конфликта все равно даст вам правильное решение.

• Мы начинаем с (0,0).
• Если значение содержится в ячейке dp[x][y+1] справа+ current grid[x][y] дает нам значение, аналогичное dp[x][y], мы движемся вправо, в противном случае мы движемся вниз.

Фрагмент:

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 + " )");

Полный код: https://ideone.com/lRZ6E5

Answer 2

Что ж, если вы пишете динамическое программирование сверху вниз (как вы это сделали), восстановление фактического ответа на самом деле очень просто.

Таким образом, у вас есть функция getForwardMax, которая для данной ячейки возвращает максимальное количество, которое мы можемсобирать движение вправо или вниз

Вы также знаете начальную позицию, поэтому все, что вам нужно сделать, это построить ответ шаг за шагом:

1. Допустим, вы находитесь в какой-то ячейке (r,c)
2. если есть только один возможный ход (вы находитесь на границе), просто сделайте это
3. в противном случае мы можем либо перейти к (r+1,c) или (r,c+1)
4. мытакже узнайте, сколько мы заработаем, перейдя в эти ячейки и пройдя путь к цели из getForwardMax function
5. Поэтому мы просто выбираем движение, которое дает лучший результат