题目链接：120. Triangle － medium
注意理解题意！
下一步必须是这一node的左子结点，或右结点，即当前列number是i，下一步只能是i或i+1.

思路参考大神，很详细：https://kingsfish.github.io/2017/08/26/Leetcode-120-Triangle/
这题的关键在于用从下向上的DP.

在思考如何解决这两个问题的时候突然想到了二维DP问题的时候空间优化方法，二维DP问题也有数值丢失的问题，而它是使用倒序来解决这个问题的。

运用到这个问题时来，我们可以把自顶向下改成自底向上，每次比较该节点两个孩子的数值大小，将小的那个孩子节点的值再加上本身节点的值即为该节点以下的最小路径和，以此类推直到顶点。这两种方式对于结果的正确性来说没有什么影响，这样的话就解决了第一个数值保存的问题，同时我们发现这样也恰好解决了第二个问题，根据此算法，最后的最小路径和肯定会存储在dp(0)，这样就省去了最后对dp的遍历时间。

此算法使用了一个一维数组用于存储结果，空间复杂度为O(n)(n为三角形层数)；同时此算法有两层循环，所以时间复杂度是O(n^2)。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null || triangle.size()== 0)return 0;
        
        int[] dp = new int[triangle.size()+1];//每一行元素数等于行num，所以最大行元素size＝＝行数;考虑最后一行开始时，size＋1
        //自下而上
        for(int i = triangle.size()-1; i>=0; i--){
            List<Integer> sublist = new ArrayList<Integer>(triangle.get(i));
            for(int j = 0; j< sublist.size(); j++){
                dp[j] = Math.min(dp[j], dp[j+1])+sublist.get(j);//start->最后一行，等于自身； 其他->min(left_path,right_path)+self
            }
        }
        return dp[0];
        
    }
}