12ms c++ solution with O(n) additional space


  • 0
    K
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            
            if (n <= 0) return 0;
            
            vector<int> d(triangle[n-1].size(), INT_MAX);       // caculate current level score
            vector<int> temp(triangle[n-1].size(), INT_MAX);    //backup up level score
            d[0] = triangle[0][0];
            temp = d;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < triangle[i].size(); j++) {
                    if (j == 0) {   // left corner
                        d[j] = temp[j] + triangle[i][j];
                    } else if (j == triangle[i].size() - 1) {   // right corner
                        d[j] = temp[j-1] + triangle[i][j];
                    } else {
                        d[j] = min(temp[j-1], temp[j]) + triangle[i][j];
                    }
                }
                temp = d;
            }
            
            // get the minimal score
            int min_val = INT_MAX;
            for (int i = 0; i < d.size(); i++){
                if (d[i] < min_val)
                    min_val = d[i];
            }
            
            return min_val;
        }
    };

  • 0
    W

    A simpler one:

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
    	if(triangle.size() == 0) return 0;
    
            vector<int> v1 = triangle[triangle.size()-1];
            
            for (int row = triangle.size()-2; row >=0; row--) {
                vector<int> v2 = v1;
                for(int k = 0; k < triangle[row].size(); k++) {
                    v2[k] = triangle[row][k] + min(v1[k], v1[k+1]);
                }
                v1.swap(v2);
            }
            return v1[0];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.