麻煩理解動態編程

我遇到過這個問題。給定一個三角形，從上到下找到最小路徑和。您可以移動到下一行的相鄰數字的每一步。麻煩理解動態編程

[ 
    [2], 
    [3,4], 
    [6,5,7], 
[4,1,8,3] 
]

這是一個動態編程的例子。但是當我來練習時，對我來說這是一個非常困難或令人困惑的概念。我看過視頻和在線閱讀教程，起初看起來很簡單，但是當我接近一個問題時，我完全迷失了方向。所以我找到了一個解決方案的在線和使用底部的方法：

public init minmumTotal(ArrayList<ArrayList<Integer>> triangle) { 
     if (triangle.size() == 0 || triangle == null) 
        return 0; 
    int[] dp = new int[triangle.size()+1]; // store each index’s total 
     for (int i = triangle.size()-1; i >=0; i--) { 
      for (int j = 0; j < triangle.get(i).size(); j++) { 
       // first round: dp[j], dp[j+1] are both 0 
       dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j); 
      } 
     } 
      return dp[0]; 
     }

似乎看透了該解決方案會後容易。但是，這可以使用自頂向下的方法來完成嗎？有人能解釋爲什麼底部方法比頂部方法更好？何時適合使用自上而下或自下而上？還有，因爲問題提到每個"Each step you may move to adjacent numbers on the row below."這是否意味着每一行迭代整列之前我進入下一行？

來源

2016-03-04 user3497437

我不確定這個解決方案是否算作動態編程，但我認爲它非常高效。

您可以從三角形的底部開始，然後通過在三角形中向上移動將其摺疊。對於下一行中的每個數字，在其下面添加兩個數字中最小的數字。當你到達頂端時，你將只有一個數字，這將是你的結果。所以，你會得到這樣的：

開始：

第1步：

2 
    3 4 
7 6 10

第2步：

2 
    9 10

第3步：

來源

2016-03-04 10:50:37 marstran

@marstan爲什麼不自上而下的方法？ – user3497437

我認爲最好從底部開始，因爲最終只有一個數字。如果從頂部開始，最終會有4個數字。然後，您需要在完成其他三個步驟後搜索最小值。 – marstran

@martan哦，你是對的 – user3497437

有點偏離主題，但如果您真的想以正確的方式處理NullPointerException，那麼該解決方案中的第一條if語句需要轉換。

所以我嘗試了自頂向下的方法，並且有幾個問題。

首先，像marstran已經說過的，你最終有更多的數字，並且需要做一個最小的搜索。

其次，自下而上的方法使用額外的數組字段，以確保它不會遇到IndexOutOfBound異常。我並沒有真正找到一種從上到下的好方法（自下而上的方法具有的優點是，您始終知道有兩個數字可以查看（左邊的孩子和右邊的孩子），自頂向下的方法有很多節點沒有右邊或左邊的父母）。所以還有一些額外的if語句。

public static int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { 
    if (triangle == null || triangle.isEmpty()) return 0; 

    int[] results = new int[triangle.size()]; 

    for (int i = 0; i < triangle.size(); i++) { 
     ArrayList<Integer> line = triangle.get(i); 

     for (int j = line.size() - 1; j >= 0; j--) { 
      if (j == 0) results[j] = line.get(j) + results[j]; 
      else if (j >= i) results[j] = line.get(j) + results[j - 1]; 
      else results[j] = line.get(j) + Math.min(results[j], results[j - 1]); 
     } 
    } 

    int minimum = results[0]; 
    for (int i = 1; i < results.length; i++) { 
     if (results[i] < minimum) { 
      minimum = results[i]; 
     } 
    } 

    return minimum; 
}

無論如何，這是儘可能接近給定的解決方案，我可以用自頂向下的方法。

請記住，沒有人強迫你只使用1d數組作爲結果。如果這個概念太難以應付，可以簡單地使用2d數組。它會增加您需要編寫的代碼量，但可能會更容易一些。

來源

2016-03-04 11:42:22

麻煩理解動態編程

回答

相關問題