麻烦理解动态编程

我遇到过这个问题。给定一个三角形，从上到下找到最小路径和。您可以移动到下一行的相邻数字的每一步。麻烦理解动态编程

[ 
    [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

麻烦理解动态编程

回答

相关问题