Triangle

Q:
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.

A:

------------从下往上来计算-----利用一个数组来保持-----

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        // bottom up build it.
        // still use the alternative list
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        all.add(new ArrayList<Integer>());
        all.add(new ArrayList<Integer>());
        
        int numRow = triangle.size();
        
        int indexAlternative = 0;
        //build the last row
        for(int i=0;i<triangle.get(numRow-1).size(); i++){
            all.get(indexAlternative).add(triangle.get(numRow-1).get(i));
        }
        
        for(int i = numRow - 2; i >= 0; i--){ // calculate each row bottom up
            ArrayList<Integer> lastList = all.get(indexAlternative);
            ArrayList<Integer> curList = all.get(1- indexAlternative);
            ArrayList<Integer> triangleRow = triangle.get(i);
            //First, we need clean the current list
            curList.clear();
            for(int j=0; j <= i;j++){
                curList.add(triangleRow.get(j)+ Math.min(lastList.get(j), lastList.get(j+1)) );
            }
            indexAlternative = 1 - indexAlternative;
        }
        //return the last, just calculated list
        return all.get(indexAlternative).get(0);
        
        
    }
}

----------------------第二遍-----------------

不利用新的空间，就在原有的数据上更改。  从下到上，每次计算，某点到最下边的sum 的最小

public class Solution { 
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0 )   return 0;
        
        List<Integer> list = triangle.get(triangle.size()-1);
        for(int i = triangle.size()-2;i>=0;i--)
            for(int j = 0;j <= i;j++)
                list.set(j, triangle.get(i).get(j) + Math.min(list.get(j),list.get(j+1)));
        
        return list.get(0);
    }
} 

Mistakes:
1: 因为i 是index， 所以，我们在上面的for(int j =0 ... )循环中， 应该是j<=i  而不是j<i
2: 第二遍的时候，因为，比较晕， 前天睡了4个小时，11点的时候，又补了1个小时。还是不清醒。 因此竟然忘记了第二层循环，哎~~~~~~~~~~


当我们在原有基础上更改的时候， 如果从上往下计算，需要注意的下标越界问题会比较tricky

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null || triangle.size()==0)
            return 0;
        int res = triangle.get(0).get(0);
        for(int i = 1;i<triangle.size();i++){
            List<Integer> p = triangle.get(i-1),  cur = triangle.get(i);
            res = Integer.MAX_VALUE; 
            for(int j=0;j<cur.size();j++){
                int minParentSum = (j==0? p.get(j) : (j==cur.size()-1? p.get(j-1) : Math.min(p.get(j), p.get(j-1)))   );
                cur.set(j, cur.get(j) + minParentSum);
                res = Math.min(res, cur.get(j));
            }
        }
        return res;
    }
}