120. Triangle

The DP algorithm with space O(n*n) is trivial. Here is the solution with O(n).

1:  class Solution {  
2:  public:  
3:    int minimumTotal(vector<vector<int>>& triangle) {  
4:      int rows = triangle.size();  
5:      if (rows == 0) return 0;  
6:      vector<int> dp(triangle[rows-1].size(), 0);  
7:      for (int i = rows-1; i >= 0; i--) {  
8:        for (int j = 0; j < triangle[i].size(); j++) {  
9:          if (i == rows-1) dp[j] = triangle[i][j];  
10:          else dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);  
11:        }  
12:      }  
13:      return dp[0];  
14:    }  
15:  };