My 12ms clear DP solution to the problem, O(n) space complexity


  • 0
    Z
    class Solution {
    public:
        int minimumTotal(vector<vector<int>> &triangle) {
            if(triangle.size()==0)
                return 0;
             if(triangle.size()==1)
                return triangle[0][0];
            vector<int> oldminpath;
            vector<int> newminpath;
            oldminpath.push_back(triangle[0][0]);
            for(int i=1;i<triangle.size();i++)
            {
                newminpath.push_back(oldminpath[0]+triangle[i][0]);
                for(int j=1;j<triangle[i].size()-1;j++)
                    newminpath.push_back(min(oldminpath[j-1]+triangle[i][j],oldminpath[j]+triangle[i][j]));
                newminpath.push_back(oldminpath[i-1]+triangle[i][i]);
                oldminpath=newminpath;
                newminpath.clear();
            }
            int mymin=oldminpath[0];
            for(int i=0;i<oldminpath.size();i++)
                if(mymin>oldminpath[i])
                    mymin=oldminpath[i];
            return mymin;
        }
    };

Log in to reply
 

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