通過矩陣的最小費用

Question

Matrix: 
6 9 3 
4 8 2 
3 5 10 

您可以從第一行的任何整數開始，只能沿矩陣向下，向左或向右，或者直接在前一個數字的下面添加。例如，你開始在9你可以去4,8或2 我想出如何得到的結果矩陣是

Matrix: 
6 9 3 
10 11 5 
13 10 15 

的最短路徑顯然是3> 2> 5對應到結果矩陣上的3> 5> 10。我想將最便宜的路徑的座標存儲在ArrayList中。在這種情況下，它將是[0,2,1,2,2,1]。這是我迄今爲止。我的問題是你在哪裏添加值到ArrayList？

 private static ArrayList<Integer> minCost(int cost[][]) 
    { 
    ArrayList<Integer> minValues = new ArrayList<>(); 
    int n = cost.length; 
    int m = cost[0].length; 
    int i, j; 
    int tc[][] = new int[m][n]; 

    for (i = 0; i <= n - 1; i++) { 
     tc[0][i] = cost[0][i]; 
    } 


    for (i = 1;i <= n - 1; i++) { 
     for (j = 0; j <= m - 1; j++) { 
      if(j ==0){ 
       tc[i][j] = Math.min(tc[i - 1][j], 
         tc[i-1][j + 1]) 
         + cost[i][j]; 
      } 
      else if(j == m-1){ 
       tc[i][j] = Math.min(tc[i - 1][j - 1], 
         tc[i - 1][j]) 
         + cost[i][j]; 
      } 
      else{ 
       tc[i][j] = min(tc[i - 1][j - 1], 
         tc[i - 1][j], 
         tc[i-1][j + 1]) 
         + cost[i][j]; 
      } 

     } 
    } 
      return minValues; 
    } 

Answer 1

在生成整個總成本矩陣後，應該在數組列表中添加值，就像您已經完成的那樣。

該路徑將被重建倒退，從具有最小總成本的底行中的位置開始。 這將是結果數組列表中的最後一對座標。

之後，它的前身應該被確定。這可以通過檢查前一行中的哪個相鄰單元具有總成本來完成，該總成本在被添加到當前單元的成本時產生期望的總成本。

在提供的示例中，最優路徑必須在單元格（2,1）的最後一行結束，因爲這是底行（總成本爲10）總成本最小的單元格。前一個單元格需要具有total_cost = 10 - cost（2，1）= 5的單元格。在第1行的相鄰單元格中有一個具有此屬性的候選單元，即單元格（1,2）。

該過程應該繼續這樣，按照相反的順序依次找到路徑的單元格，直到路徑完成（即它到達第一行）。

---

一些言論：

• ，如果在某一點上，有多個最佳候選前身（兩者以相同的總擁有成本），那麼任何人都可以選擇。它們中的每一個都會生成最佳路徑，總成本相同。按照期望的順序創建最終路徑，在每個步驟中找到的位置可以添加到數組的前面（以避免需要在末尾執行反轉）。