最小コストのための最適なグリッドパスの記録

Question

したがって、私は2次元マトリックスを持ち、最小コストを与えるパスを記録することになっています。私は下にまたは右に移動することができます。例：

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

解決策の最初の部分は正しいように見えますが、2番目の部分は正しくありません。

ネストされたforループの実行後、solutionGrid内の各位置には、その位置に到達するための最小コストが設定されます。

したがって、開始から終了までの最小コストのパスを決定するには、フィニッシュから開始し、開始に達するまで左または上に移動する必要があります。現在の位置の左にあるソリューショングリッド内の位置が現在の位置よりも上のソリューショングリッド内の位置よりも小さいときは、左に移動する必要があります。

これを実行しましたが、正しいパスが左または上に移動すると宣言するのではなく、右または下に移動していると宣言しています。

回答リストは、最初からフィニッシュに到達する方法を指示する必要があるため、回答リストは正しいが逆の順序になります。

代わりに「追加」を用いる方法の

answers.insert(0, "right") 

と

answers.insert(0, "down") 

を呼び出すことによって、あなたのプログラムを修正 - あなたの配列リストの末尾に追加します。