Triangle (LeetCode Array)

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.

Idea: Dynamic programming. We have the distance from (i,j) to the bottom is dis(i,j)=Math.min(dis(i+1, j),dis(i+1, j+1))+valueAt(i, j). So we can fill the table from bottom to up, but adding an empty (all 0's) row at the bottom. Each row i has i+1 numbers. This algorithm will cost O(n^2) space.
However, we need an O(n) space algorithm. We can observe that to fill the block dis(i, j), we need the results from dis(i+1, j) and dis(i+1, j+1); to fill the block dis(i, j+1), we only need the result of dis(i+1, j+1) and dis(i+1, j+2), where dis(i+1,j) is no longer needed. So we can reuse the space at dis(i+1, j) by store the result of dis(i, j) at the same place of dis(i+1, j). Then we just need an one-dimension array to cache the results.

Time: O(n^2) Space: O(n)

Code:

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