我遇到了这个问题。给定一个三角形，找到从上到下的最小路径总和。您可以将每一步移至下面一行中的相邻数字。
[
[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."是否意味着对于每一行，在我进入下一行之前都要迭代整列？ 最佳答案
我不确定该解决方案是否算作动态编程，但我认为它非常有效。
您可以从三角形的底部开始，然后通过在三角形中向上移动来折叠它。对于下一行中的每个数字，在其下面添加两个数字中的最小数字。到达顶部时，只有一个数字，这就是结果。所以你会得到这个：
开始：
2
3 4
6 5 7
4 1 8 3
步骤1：
2
3 4
7 6 10
第2步：
2
9 10
第三步：
11