|
| 1 | +packagemedium; |
| 2 | +importjava.util.*; |
| 3 | +publicclassTriangle { |
| 4 | + |
| 5 | +publicstaticintminimumTotal(List<List<Integer>>triangle) { |
| 6 | +/**Looked at this post: https://discuss.leetcode.com/topic/1669/dp-solution-for-triangle, @stellari has a very excellent explanation. |
| 7 | + * Basically, we use the bottom-up approach, starting from the bottom row of this triangle, and we only need to store the shortest path of each node |
| 8 | + * from its last row, and keep overwriting it until we reach the top.*/ |
| 9 | +intn =triangle.size(); |
| 10 | +List<Integer>cache =triangle.get(n-1); |
| 11 | + |
| 12 | +for (intlayer =n-2;layer >=0;layer--){//for each layer |
| 13 | +for (inti =0;i <=layer;i++){//check its very node |
| 14 | +intvalue =Math.min(cache.get(i),cache.get(i+1)) +triangle.get(layer).get(i); |
| 15 | +cache.set(i,value); |
| 16 | + } |
| 17 | + } |
| 18 | +returncache.get(0); |
| 19 | + } |
| 20 | + |
| 21 | +publicstaticvoidmain(String...strings){ |
| 22 | +List<List<Integer>>triangle =newArrayList(); |
| 23 | +triangle.add(Arrays.asList(1)); |
| 24 | +triangle.add(Arrays.asList(2,3)); |
| 25 | +System.out.println(minimumTotal(triangle)); |
| 26 | + } |
| 27 | + |
| 28 | +} |