<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 dp[2001][2001];

    // Recursive function to solve the problem
    int solve(vector<vector<int>>& pairs, int idx, int prev) {
        if(idx >= size(pairs)) {
            return 0;  // Base case: No more pairs to consider
        }
        if(prev!=-1000&&dp[idx][prev] != -1) {  // Check if the subproblem is already solved
            return dp[idx][prev];
        }
        int take = 0;
        if(prev < pairs[idx][0]) {  // If the current pair can be taken
            take = 1 + solve(pairs, idx + 1, pairs[idx][1]);
        }
        int nottake = solve(pairs, idx + 1, prev);  // Skip the current pair
        if(prev!=-1000)
        return dp[idx][prev] = max(take, nottake); 
        return  max(take, nottake); // Store and return the result
    }

    int findLongestChain(vector<vector<int>>& pairs) {
        memset(dp, -1, sizeof(dp));  // Correct usage of memset

        // Sorting pairs based on the first element (default behavior)
        sort(begin(pairs), end(pairs));

        // Adjusting the pair values to ensure all indices are non-negative
        for(auto &it : pairs) {
            it[0] += 1000;
            it[1] += 1000;
        }

        // Initial call to solve with prev initialized to 1000 to allow the first pair to be considered
        return solve(pairs, 0, -1000);
    }
};

40666