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 usedp[j-1]-triangle[i][j-1] to update dp[j], because dp[j-1] maybe updated bydp[j-2].

Loading Disqus comments...
Table of Contents