Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
一刷
題解：
dynamic programming, 這題不能用自頂向下只能用從下到上杜顺，因為為了更新dp[i]但不能利用到已被影響到的dp[i-1]的值图云。
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0)
return 0;
int rowNum = triangle.size();
List<Integer> lastRow = triangle.get(rowNum - 1);
int[] paths = new int[rowNum];
for(int i=0; i<lastRow.size(); i++){
paths[i] = lastRow.get(i);
}
for(int i = rowNum-2; i>=0; i--){
for(int j = 0; j < triangle.get(i).size(); j++){
paths[j] = triangle.get(i).get(j) + Math.min(paths[j], paths[j+1]);
}
}
return paths[0];
}
}
二刷
dp
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int deep = triangle.size();
if(deep == 1) return triangle.get(0).get(0);
int[] dp = new int[triangle.get(deep-1).size()];
for(int i=0; i<dp.length; i++){
dp[i] = triangle.get(deep-1).get(i);
}
for(int layer = deep-2; layer>=0; layer--){
for(int i=0; i<=layer; i++){
//find the lesser ot its two children, and sum the current value in the triangle with it
dp[i] = Math.min(dp[i], dp[i+1]) + triangle.get(layer).get(i);
}
}
return dp[0];
}
}
