packagemedium;

importjava.util.*;

publicclassTriangle {

publicstaticintminimumTotal(List<List<Integer>>triangle) {

intn =triangle.size();

List<Integer>cache =triangle.get(n-1);

for (intlayer =n-2;layer >=0;layer--){//for each layer

for (inti =0;i <=layer;i++){//check its very node

intvalue =Math.min(cache.get(i),cache.get(i+1)) +triangle.get(layer).get(i);

cache.set(i,value);

}

}

returncache.get(0);

}

publicstaticvoidmain(String...strings){

List<List<Integer>>triangle =newArrayList();

triangle.add(Arrays.asList(1));

triangle.add(Arrays.asList(2,3));

System.out.println(minimumTotal(triangle));

}

}

|125|[Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)|[Solution](../../blob/master/EASY/src/easy/ValidPalindrome.java)| O(n)|O(1) | Easy| Two Pointers

|122|[Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)|[Solution](../../blob/master/MEDIUM/src/medium/BestTimeToBuyAndSellStockII.java)| O(n)|O(1) | Medium | Greedy

|121|[Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)|[Solution](../../blob/master/EASY/src/easy/BestTimeToBuyAndSellStock.java)| O(n)|O(1) | Easy| DP

|120|[Triangle](https://leetcode.com/problems/triangle/)|[Solution](../../blob/master/MEDIUM/src/medium/Triangle.java)| O(m*n)|O(n) | Medium| DP

|119|[Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/)|[Solution](../../blob/master/EASY/src/easy/PascalsTriangleII.java)| O(n^2)|O(1)| Easy|

|118|[Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)|[Solution](../../blob/master/EASY/src/easy/PascalsTriangle.java)| O(n^2)|O(1)| Easy|

|117|[Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)|[Solution](../../blob/master/HARD/src/hard/PopulatingNextRightPointersinEachNodeII.java)| O(n)|O(1) | Hard| BFS