[LeetCode] Triangle

Problem:

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.

Solution:O(n)

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle==null || triangle.size()==0) 
            return 0;
        ArrayList<Integer> ret = new ArrayList<>();
        for(int i=0;i<triangle.size();i++){
            ArrayList<Integer> tmp = triangle.get(i);
            ret.add(0,i>0?tmp.get(0)+ret.get(0):tmp.get(0));
            for(int j=1;j<ret.size()-1;j++){
                ret.set(j,Math.min(ret.get(j),ret.get(j+1))+tmp.get(j));
            }
            if(ret.size()>1)
                ret.set(ret.size()-1,ret.get(ret.size()-1)+tmp.get(ret.size()-1));
        }
        
        int min=Integer.MAX_VALUE;
        for(Integer tmp:ret){
            min=Math.min(tmp,min);
        }
        return min;
    }
}

Key Concept:DP and use O(n) spaces to save previous rsult