My C++ solution, O(n) space, accepted for 8ms


  • 3
    Z
    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            int m=triangle.size();
            vector<int> res;
            res.push_back(triangle[0][0]);
            
            for(int i=1;i<m;i++){
                vector<int> temp(i+1);
                temp[0]=res[0]+triangle[i][0];
                temp[i]=res[i-1]+triangle[i][i];
                
                for(int j=1;j<i;j++)
                temp[j]=res[j-1]>res[j]?(res[j]+triangle[i][j]):(res[j-1]+triangle[i][j]);
                
                res=temp;
            }
            
            int min=res[0];
            for(int j=1;j<m;j++){
                if(res[j]<min)
                min=res[j];
            }
            return min;
        }
    };
    

    I use O(n) space instead of O(1) space, because I don't think modifying the original data "triangle" is always a good choice.


  • 0
    O

    But actually res and temp both uses O(N) space right?


  • 2
    B

    I modify your code and remove the temp to use less space.

    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            int m=triangle.size();
            vector<int> res(m,0);
            res[0]=triangle[0][0];
    
            for(int i=1;i<m;i++){
                res[i]=res[i-1]+triangle[i][i];
                for(int j=i-1;j>0;j--)
                res[j]=res[j-1]>res[j]?(res[j]+triangle[i][j]):(res[j-1]+triangle[i][j]);
                
                res[0]=res[0]+triangle[i][0];
            }
    
            int min=res[0];
            for(int j=1;j<m;j++){
                if(res[j]<min)
                min=res[j];
            }
            return min;
        }
    };

  • 1
    R

    I am lazy. in place solution (sometimes it's not good for destroying the original input)

    int minimumTotal(vector<vector<int> > &triangle) {
        if (triangle.empty()) return 0;
        for (int i = triangle.size() - 2; i >=0; --i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
    

    OK, now it's the O(n) space solution, just add one line of code

    int minimumTotal(vector<vector<int> > &triangle) {
        if (triangle.empty()) return 0;
        vector<int> v(triangle.back());
        for (int i = triangle.size() - 2; i >=0; --i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                v[j] = min(v[j], v[j+1]) + triangle[i][j];
            }
        }
        return v[0];
    }
    

Log in to reply
 

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