<p>You are given an array of <code>n</code> pairs <code>pairs</code> where <code>pairs[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> and <code>left<sub>i</sub> &lt; right<sub>i</sub></code>.</p>

<p>A pair <code>p2 = [c, d]</code> <strong>follows</strong> a pair <code>p1 = [a, b]</code> if <code>b &lt; c</code>. A <strong>chain</strong> of pairs can be formed in this fashion.</p>

<p>Return <em>the length longest chain which can be formed</em>.</p>

<p>You do not need to use up all the given intervals. You can select pairs in any order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> pairs = [[1,2],[2,3],[3,4]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The longest chain is [1,2] -&gt; [3,4].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> pairs = [[1,2],[7,8],[4,5]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest chain is [1,2] -&gt; [4,5] -&gt; [7,8].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == pairs.length</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>-1000 &lt;= left<sub>i</sub> &lt; right<sub>i</sub> &lt;= 1000</code></li>
</ul>

class Solution {
public:
    int helper(vector<vector<int>>& pairs, int ind, int prevind, vector<vector<int>>& dp){
        if(ind == pairs.size()) return 0;

        if(prevind != -1 && dp[ind][prevind] != -1)
            return dp[ind][prevind];

        int take = 0, notTake = 0;
        if(prevind == -1 || pairs[prevind][1] < pairs[ind][0]){
            take = 1 + helper(pairs, ind+1, ind, dp); 
        }
        notTake = helper(pairs, ind+1, prevind, dp);
        if(prevind != -1)
            dp[ind][prevind] = max(take, notTake);
        return max(take, notTake);
    }
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());
        // Top Down || Memoization
        vector<vector<int>> dp(n, vector<int> (n, -1));
        return helper(pairs, 0, -1, dp);

        //Bottom Up || Tabulation
        // vector<int> dp(n, 1);
        // int mx = 1;
        // sort(pairs.begin(), pairs.end());
        // for(int i=0; i<n; i++){
        //     for(int j=0; j<i; j++){
        //         if(pairs[i][0] > pairs[j][1]){
        //             dp[i] = max(dp[i], dp[j] + 1);
        //         }
        //     }
        //     mx = max(dp[i], mx);
        // }
        // return mx;
    }
};
97220