120. Triangle

    /*
     * 120. Triangle
     * 12.20 by Mingyang
     * 需要自底向上求解。
     * 递推公式是：min[i+1][j]=Math.min(min[i][j],min[i][j-1])
     * 由于是三角形，且历史数据只在计算最小值时应用一次，所以无需建立二维数组
     * 这道题目非常巧妙的用了自底向上，同时也仅仅用了一个数组
     * 最后第一位只有一个数了，自然就是dp[0]
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1)
            return triangle.get(0).get(0);        
        int[] dp = new int[triangle.size()];
        //initial by last row 
        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
            dp[i] = triangle.get(triangle.size() - 1).get(i);
        }     
        // iterate from last second row
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        } 
        return dp[0];
    }
    //如果不用自底向上的解法，需要一个二维数组
    public int minimumTotal1(List<List<Integer>> triangle) {
        int size=triangle.size();
        int [][] min=new int[size][size];//to record the min path value;
        min[0][0]=triangle.get(0).get(0);
        for(int i=0;i<size-1;i++){
            for(int j=0;j<=i+1;j++){   // top to down
                if(j==0)min[i+1][j]=min[i][j]+triangle.get(i+1).get(j);
                else if(j==i+1)min[i+1][j]=min[i][j-1]+triangle.get(i+1).get(j); 
                else min[i+1][j]=Math.min(min[i][j],min[i][j-1])+triangle.get(i+1).get(j);
            }
        }
        int out=Integer.MAX_VALUE;
        for(int i=0;i<size;i++){
            if(min[size-1][i]<out)out=min[size-1][i];
        }
        return out;
    }