Question:

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.

Thinking:
It’s a simple dynamic programming question. The expression is dp[i][j] = min(d[i-1][j-1], d[i][j]) + triangle[i][j].

But the first time, my code is time exceed:

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int lr = triangle.size();
        if(lr == 0){
            return 0;
        }
        int lc = triangle.get(lr-1).size();
        int min = 100000;
        for(int i = 0; i < lc; i++){
            int tmp = dp(triangle, lr-1, i);
            if(tmp < min)
                min = tmp;
        }
        return min;
    }

    public int dp(List<List<Integer>> triangle, int row, int column){
        if(row == 0){
            return triangle.get(0).get(0);
        }
        int value = triangle.get(row).get(column);
        int size = triangle.get(row-1).size();
        if(column >= size){
            return dp(triangle, row-1, column-1) + value;
        }
        else if(column - 1 < 0){
            return dp(triangle, row-1, column) + value;
        }
        else{
            int res1 = dp(triangle, row-1, column-1) + value;
            int res2 = dp(triangle, row-1, column) + value;
            if(res1 < res2){
                return res1;
            }
            else{
                return res2;
            }
        }
    }
}

Then I noticed the bonus, so I change my mind to use iteration:

public class Solution{
    public int minimumTotal(List<List<Integer>> triangle){
        int lr = triangle.size();
        int[] min = new int[lr];
        int[] tempmin = new int[lr];
        min[0] = triangle.get(0).get(0);
        for(int i = 1; i < lr; i++){
            tempmin[0] = min[0] + triangle.get(i).get(0);
            tempmin[i] = min[i-1] + triangle.get(i).get(i);
            for(int j = 1; j < i; j++){
                int res1 = min[j-1] + triangle.get(i).get(j);
                int res2 = min[j] + triangle.get(i).get(j);
                if(res1 < res2)
                    tempmin[j] = res1;
                else
                    tempmin[j] = res2;
            }
            for(int k = 0; k < i+1; k++){
                min[k] = tempmin[k];
            }
        }
        int m = 100000;
        for(int i = 0; i < lr; i++){
            if(min[i] < m)
                m = min[i];
        }
        return m;
    }
}