LintCode 数字三角形题目分析1 （常规的动态规划解法）分析2 （如果你只用额外空间复杂度O(n)的条件）

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        // write your code here
         //从底往上，把每一行的元素改为其下一行能与之相加的两个数得到的和的最小值
        int row = triangle.length;
        //int col = triangle[row-1].length;
        if(row < 0)
            return row;
        if(row == 1)
            return triangle[0][0];
        int[][] dp = new int[row+1][row+1];
        dp[0][0] = triangle[0][0];
        for(int i=1; i<row; i++) {  
            dp[i][0] = dp[i-1][0]+triangle[i][0];  
        }
        for(int i=1; i<row; i++) {  
            dp[i][i] = dp[i-1][i-1]+triangle[i][i];  
        }
        for(int i=2;i<row;i++)
            for(int j=1;j<i;j++)
                dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
        
        int min = dp[row-1][0];
        for(int i=1;i<row;i++)
        {
            if(dp[row-1][i]< min)
                min = dp[row-1][i];
        }
            
        return min;
    }

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        // write your code here
         //从底往上，把每一行的元素改为其下一行能与之相加的两个数得到的和的最小值
        int row = triangle.length;
        
        if(row < 1){
            return 0;
        }
        
        if(row == 1){
            return triangle[0][0];
        }
        
        for(int i=row-2;i>=0;i--){
            for(int j=0;j<triangle[i].length;j++){
                int min = Math.min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j];
                triangle[i][j] = min;
            }
        }
        
        return triangle[0][0];
    }
}