题目链接：https://leetcode.cn/problems/maximum-length-of-pair-chain/description/
题目大意：给出一系列区间pairs[][]，如果某两个区间[a, b], [c, d]满足b < c，这两个区间就可以串起来[a, b] -> [c, d]。求能够串起来的区间的最大长度。
思路：看起来就很适合用DFS做的题。刚开始还想着用一个二维数组存区间之间的连接关系，后来发现，如果按照左端点排序的话，那么这些区间有两个特点
- 明显
pair[i]只能连接pair[j], j > i。也就是一个区间只可能连接后面的区间。 - 如果区间
pair[i]能够连接到pair[j]，那么所有后面的k >= j的区间也都能被pair[i]连接。
因此，对每个区间，我们首先找到最近的下一个能连接的区间（因为这样才能让串起来的区间最长），存在min_next[]里。
for (int i = 0; i < n; i++) {for (int j = i+1; j < n; j++) {if (pairs[i][1] < pairs[j][0]) {min_next[i] = j;break;} }}
随后DFS，cnt表示加入了pair[idx]以后串当前暂时的长度。tmp用来存如果当前串接了后续的区间后最长的之后的串长。因此返回的是tmp。另外，我们把以i开头的串的最长长度存在longest[i]中，需要时直接取，不用再DFS到底一次。
int DFS(int idx, int cnt) {cnt++;int tmp = cnt;for (int j = min_next[idx]; j < n; j++) {if (longest[j] != 0)tmp = max(tmp, 1+longest[j]);elsetmp = max(tmp, DFS(j, cnt));}return tmp;}
但是我们发现，因为最后的区间必然是不可能连接到其他区间的，而其他靠后的区间也更少可能连接到后面的区间，因此实际上如果从后往前遍历的话，所有的longest[i]都可以正确顺利地求出来，也就不用什么DFS了（或者说相当于从搜索树的底部往上爬）
for (int i = n-1; i >= 0; i--) {int tmp = 0;for (int j = min_next[i]; j < n; j++)tmp = max(tmp, longest[j]);longest[i] = 1 + tmp;}
完整代码
class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end(), [&](vector<int>& x, vector<int>& y) -> bool {if (x[0] != y[0])return x[0] < y[0];elsereturn x[1] < y[1];});int n = pairs.size();vector<int> min_next(n, 1001);vector<int> longest(n, 1); for (int i = 0; i < n; i++) {for (int j = i+1; j < n; j++) {if (pairs[i][1] < pairs[j][0]) {min_next[i] = j;break;} }}for (int i = n-1; i >= 0; i--) {int tmp = 0;for (int j = min_next[i]; j < n; j++)tmp = max(tmp, longest[j]);longest[i] = 1 + tmp;}return *max_element(longest.begin(), longest.end());}
};
