# triangle

## triangle

### DP

dp[i][j] means the minnum value in position i,j

`````` 1 class Solution {
2 public:
3     int minimumTotal(vector<vector<int> > &triangle) {
4         int n = triangle.size();
5         if ( 0 == n ) {
6             return 0;
7         }
8         int dp[n][n];
9         memset(dp,0,sizeof(dp));
10         dp[0][0] = triangle[0][0];
11         for ( int i = 1; i < n; i++ ) {
12             for ( int j = 0; j <= i; j++ ) {
13                 if ( 0 == j ) {
14                     dp[i][j] = dp[i-1][j]+triangle[i][j];
15                 } else if ( j == i ) {
16                     dp[i][j] = dp[i-1][j-1]+triangle[i][j];
17                 } else {
18                     dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
19                 }
20             }
21         }
22         int result = dp[n-1][0];
23         for ( int i = 1; i < n; i++ ) {
24             result = min(dp[n-1][i],result);
25         }
26         return result;
27     }
28 };``````

### Space time complexity saved

We can only use O(n) spae time complexity to resolve this problem. The previous problem show that after updating the level i, level i-1 become useless.

`````` 1 class Solution {
2 public:
3     int minimumTotal(vector<vector<int> > &triangle) {
4         int n = triangle.size();
5         if ( 0 == n ) {
6             return 0;
7         }
8         int dp[n];
9         memset(dp,0,sizeof(dp));
10         dp[0] = triangle[0][0];
11         for ( int i = 1; i < n; i++ ) {
12             int pre = dp[0];
13             for ( int j = 0; j <= i; j++ ) {
14                 if ( 0 == j ) {
15                     dp[j] += triangle[i][j];
16                 } else if ( j == i ) {
17                     dp[j] = pre+triangle[i][j];
18                 } else {
19                     int t = dp[j];
20                     dp[j] = min(pre,dp[j])+triangle[i][j];
21                     pre = t;
22                 }
23             }
24         }
25         int result = dp[0];
26         for ( int i = 1; i < n; i++ ) {
27             result = min(dp[i],result);
28         }
29         return result;
30     }
31 };``````

Attention!When j is nether equal to 0 or i, we can not use`dp[j-1]-triangle[i][j-1]` to update `dp[j]`, because `dp[j-1]` maybe updated by`dp[j-2]`.