C++ recursive DP solution


  • -2
    Z
    bool compare(pair<int,int> &p1,pair<int,int> &p2){
        return p1.first<p2.first;
    }
    class Solution {
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes) {
            int sz=envelopes.size();
            if(sz<2)return sz;
            sort(envelopes.begin(),envelopes.end(),compare);
            envelopes.insert(envelopes.begin(),pair<int,int> (0,0));
            sz++;
            vector<int> table (sz,0);
            return findDoll(envelopes,0,table)-1;
        }
        
        int findDoll(vector<pair<int,int>> &envelopes,int idx,vector<int> &table){
            if(idx==envelopes.size()-1)return 1;
            int maxDoll=0,doll;
            for(int i=idx+1;i<envelopes.size();i++){
                if(envelopes[i].first>envelopes[idx].first && envelopes[i].second>envelopes[idx].second){
                    doll=table[i]?table[i]:findDoll(envelopes,i,table);
                    maxDoll=max(maxDoll,doll);    
                }
            }
            maxDoll++;
            table[idx]=maxDoll;
            return maxDoll;
        }
    };
    

    By inserting a (0,0) envelope at the beginning of the sorted list, turn the question into recursively looking for the longest Russian doll start with the first element in the list.


Log in to reply
 

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