https://leetcode.com/problems/triangle/description/
解题思路：
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
代码：
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null) return 0;
int row = triangle.size();
int col = triangle.get(row - 1).size();
int[] dp = new int[col + 1];
for(int i = row - 1; i >= 0; i--){
for(int j = 0; j < triangle.get(i).size(); j++){
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
网友评论