java - 以最低成本记录最佳网格路径

Question

所以我有一个二维矩阵，我应该记录给出最小成本的路径。我只能向下或向右移动。示例:

2 4 1
3 7 6
3 8 9

Output: right right down down

我的代码给出了不正确的答案，但我无法找出原因。我还在下面附上了我的代码:

public static List<String> optimalGridPath(int[][] grid) {

    ArrayList<String> answers = new ArrayList<String>();
    //TODO
    int gridRows = grid.length-1;
    int gridColumns = grid[0].length-1;

    int solutionGrid[][] = new int[gridRows+1][gridColumns+1];

    for (int i = 0; i <= gridRows; i++) {
        for (int j = 0; j <= gridColumns; j++) {
            if (i > 0 && j > 0)
                solutionGrid[i][j] = grid[i][j] +
                        Math.min(solutionGrid[i-1][j], solutionGrid[i][j-1]);
            else if (j == 0 && i == 0)
                solutionGrid[i][j] = grid[i][j];
            else if (j > 0)
                solutionGrid[i][j] = grid[i][j] + solutionGrid[i][j-1];
            else
                solutionGrid[i][j] = grid[i][j] + solutionGrid[i-1][j];
        }
    }

    while (gridRows != 0 && gridColumns != 0) {
        if (gridColumns == 0) {
            answers.add("down");
            gridRows--;
        }
        else if (gridRows == 0) {
            answers.add("right");
            gridColumns--;
        }
        else {
            if (solutionGrid[gridRows][gridColumns-1] <
                    solutionGrid[gridRows-1][gridColumns]) {
                answers.add("right");
                gridColumns--;
            }
            else {
                answers.add("down");
                gridRows--;
            }
        }
    }

    return answers;
}

Answer 1

您的解决方案的第一部分似乎是正确的，但第二部分不正确。

在执行嵌套的 for 循环后，solutionGrid 中的每个位置都将填充到达该位置的最低成本。

因此，要确定从起点到终点的最小成本路径，您应该从终点开始，向左或向上移动，直到到达起点。当当前位置左侧的解决方案网格中的位置小于当前位置上方的解决方案网格中的位置时，您应该向左移动。

你已经这样做了，但你并没有声明正确的路径是向左或向上移动，而是声明你正在向右或向下移动。

因为您的答案列表应该规定如何从头开始到达终点，所以您的答案列表是正确的，但顺序相反。

通过调用修复你的程序

answers.insert(0, "right")

和

answers.insert(0, "down")

而不是使用“添加”方法 - 它将附加到数组列表的末尾。