Leetcode 120 Triangle

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.

Solution 1: simple DP question. optimize the space to O(n).

 public class Solution {  
   public int minimumTotal(List<List<Integer>> triangle) {  
     int n=triangle.size();  
     int[] dp=new int[n];  
     for (int i=0; i<n; i++) {  
       int pre=0;  
       for (int j=0; j<=i; j++) {  
         int temp=dp[j];  
         if (i==0) dp[j]=triangle.get(i).get(j);  
         else {  
           int min=Integer.MAX_VALUE;  
           if (j-1>=0) min=pre;  
           if (j<=i-1 && dp[j]<min) min=dp[j];  
           dp[j]=min+triangle.get(i).get(j);  
         }  
         pre=temp;  
       }  
     }  
     int res=Integer.MAX_VALUE;  
     for (int i=0; i<n; i++) res=Math.min(res,dp[i]);  
     return res;  
   }  
 }