Also habe ich eine 2D-Matrix, und ich soll den Pfad aufzeichnen, der die minimalen Kosten ergibt. Ich kann nur nach unten oder nach rechts gehen. Beispiel:Den optimalen Gitterweg für minimale Kosten aufzeichnen
2 4 1
3 7 6
3 8 9
Output: right right down down
Mein Code gibt die falschen Antworten, aber ich bin nicht in der Lage, warum zu erkennen. Ich habe auch meinen Code unten angehängt:
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;
}
Es ist so dumm, den Fehler hier nicht zu erkennen ..... es funktioniert jetzt perfekt. Vielen Dank! –