# 0120. Triangle
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/triangle/
## 思路
令```ans[i][j]```是从起点到```triangle[i][j]```所有路径的最小权重和

注意边界
## Code

class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
List<Integer> ans = new ArrayList<>();
ans.add(triangle.get(0).get(0));
int n = triangle.size();
for(int i=1; i<n; i++){
List<Integer> temp = new ArrayList<>();
for(int j=0; j<i+1; j++){
int next = triangle.get(i).get(j);
if(j==0) temp.add(ans.get(0)+next);
else if(j==i) temp.add(ans.get(j-1)+next);
else temp.add(Math.min(ans.get(j-1), ans.get(j))+next);
}
ans = temp;
}
int res = Integer.MAX_VALUE;
for(int i=0; i<n; i++) res = Math.min(res, ans.get(i));
return res;
}
}