Russian Doll Envelopes | Easy DP solution | simple trick explained !!!
The trick is, we first sort the envolopes based on their width, Then the problem now turned into finding longest Increasing subsequence(LIS), so we just need to
The trick is, we first sort the envolopes based on their width, Then the problem now turned into finding **longest Increasing subsequence(LIS**), so we just need to find **LIS on heights of envolopes** but including some edges cases. \nLets see the edge cases to understand it more..\nconsider, `envolope = [[2,3],[5,8],[3,6],[5,7]]`, if we sort based on `compare function`, we get `[[2,3],[3,6],[5,7],[5,8]]`\nNow, if perform LIS on heights, **LIS=4, but answer should be 3**, to tackle this we take `en[i][0] > en[j][0] && en[i][1]>en[j][1]` as our condition instead of `en[i][1]>en[j][1]` inorder to make sure both width and height increasing.\n\n**Do Upvote** if you like the code and comment down if you are facing some difficulty or having some queries.\nGo through the code below for better understanding !!!\n\n\n```\nclass Solution {\npublic:\n    static bool compare(vector<int>a,vector<int>b){\n        if(a[0] == b[0]) return a[1]<b[1];\n        return a[0]<b[0];\n    }\n    int maxEnvelopes(vector<vector<int>>& en) {\n        sort(en.begin(),en.end(),compare);\n        int n = en.size(),res=1;\n        vector<int>dp(n,1);\n        for(int i=0;i<n;i++){\n            for(int j=i-1;j>=0;j--){\n                if(en[i][0] > en[j][0] && en[i][1]>en[j][1]){\n                    dp[i] = max(dp[i],dp[j]+1);\n                    res = max(res,dp[i]);\n                }\n            }\n        }\n        return res;\n    }\n};\n```
[]