LeetCode

这道题，采用动态规划算法。from top to down，把到每个节点的最小路径和都求出来。

下面是AC代码：

/**
     * Given a triangle, find the minimum path sum from top to bottom. 
     * Each step you may move to adjacent numbers on the row below.
     * @param triangle
     * @return
     */
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle){
        if(triangle==null || triangle.size()<=0)
            return 0;
        if(triangle.size() == 1)
            return triangle.get(0).get(0);
        ArrayList<Integer> last = triangle.get(0);
        ArrayList<Integer> curr = new ArrayList<Integer>();
        //through Dynamic programming 
        for(int i=1;i<triangle.size();i++){
            curr.add(last.get(0)+triangle.get(i).get(0));
            for(int j=1;j<i;j++){
                //get the smaller adjacent one on the last row 
                curr.add((last.get(j-1)<last.get(j)?last.get(j-1):last.get(j))+triangle.get(i).get(j));
            }
            curr.add(last.get(i-1)+triangle.get(i).get(i));
            last.clear();
            last.addAll(curr);
            curr.clear();
        }
        
        int min = Integer.MAX_VALUE;
        for(int i=0;i<last.size();i++){
            if(last.get(i)<min)
                min = last.get(i);
        }
        return min;
    }