DP Solution (Bottom up, C++ 6ms 4 Meaningful lines)


  • 1
    N

    My method is adding the minimum of two consecutive bottom line numbers to the corresponding second last line items. Updating the second last line and remove the bottom line. The second last line represents the partial minimum sum. After iteration, there will be only top line left, which is the sum of the total minimum.

    This is my first post. My explanation may not be so clear. Please let me know if need any clarifications.

    """

    class Solution {
    public:

    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>> tri = triangle; 
        if (tri.size()==0) return 0;
        while (tri.size()!=1){
            vector<int> bottom = tri.back(); 
            tri.pop_back(); //remove bottom line
            vector <int>& lb = tri.back();// second last line
            
            for (int j = 0; j<lb.size();j++)
            { // updating second last line
                if(bottom[j]<bottom[j+1]) lb[j] += bottom[j]; 
                else lb[j] += bottom[j+1];
            }
        }
        return tri[0][0];
    }
    

    };

    """


Log in to reply
 

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