Enregistrement du chemin de grille optimal pour un coût minimum

Question

J'ai donc une matrice 2D, et je suis censé enregistrer le chemin qui donne le coût minimum. Je peux seulement descendre ou à droite. Exemple:

2 4 1 
3 7 6 
3 8 9 

Output: right right down down 

Mon code donne les réponses incorrectes mais je ne suis pas en mesure de déterminer pourquoi. J'ai également joint mon code ci-dessous:

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

La première partie de votre solution semble être correcte, mais la deuxième partie ne l'est pas. Après l'exécution de vos boucles for imbriquées, chaque position dans votre solutionGrid sera remplie avec le coût minimum pour arriver à cette position.

Par conséquent, pour déterminer le chemin de coût minimum entre le départ et l'arrivée, vous devez commencer à l'arrivée et vous déplacer vers la gauche ou vers le haut jusqu'au début. Vous devez vous déplacer vers la gauche lorsque la position dans la grille de solution à gauche de la position actuelle est inférieure à la position dans la grille de solution au-dessus de votre position actuelle.

Vous l'avez fait, mais au lieu de déclarer que le chemin correct doit se déplacer vers la gauche ou vers le haut, vous déclarez que vous vous déplacez vers la droite ou vers le bas. Comme votre liste de réponses doit indiquer comment accéder à l'arrivée depuis le début, votre liste de réponses est correcte, mais dans l'ordre inverse.

Fix votre programme en appelant

answers.insert(0, "right") 

et

answers.insert(0, "down") 

au lieu d'utiliser la méthode « ajouter » - ce qui ajoutera à la fin de votre liste de tableau.