120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[ 
           [2], 
          [3,4], 
         [6,5,7], 
        [4,1,8,3]
]

The minimum path sum from top to bottom is 11
(i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

设状态为 f[i][j]，表示根到节点(i,j)的最短路径，状态方程：
f[i][j] = min(f[i-1,j-1],f[i-1,j]) + tringal[i,j]
使用一维数组实现：

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int height = triangle.size();
        if(height == 0){
            return 0;
        }
        
        int [] minPath = new int[height+1];
        List<Integer> layer = triangle.get(0);
        minPath[0] = Integer.MAX_VALUE;
        minPath[1] = layer.get(0);
        int minPathValue = Integer.MAX_VALUE;
        for(int i = 1; i<height; i++){
            layer = triangle.get(i);
            minPath[i+1] = Integer.MAX_VALUE;
            for(int j=i+1; j>0; j--){
                minPath[j] = Math.min(minPath[j-1], minPath[j]) + layer.get(j-1);
            }
        }
        for(Integer i: minPath){
            minPathValue = Math.min(minPathValue, i);
        }
        
        return minPathValue;
    }
}