---
# System prepended metadata

title: 0120. Triangle
tags: [Leetcode, Dynamic Programming, Medium]

---

# 0120. Triangle
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/triangle/
## 思路
令```ans[i][j]```是从起点到```triangle[i][j]```所有路径的最小权重和
```ans[i][j] = Math.min(ans[i-1][j-1], ans[i-1][j])+triangle[i][j]```
注意边界
## Code
```java=
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;
    }
}
```