【贪心 || 动态规划】最长对数链
题目
方法一（推荐）：贪心算法
思路： 贪心算法的代码并不难写，关键是难想，下面介绍，本题如何贪心及为什么可以贪心
- 就数对中第二个数进行排序 然后遍历排好序数组，判断 是否满足题意
（满足跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面） - 满足题意，结果count++， 并且跟新临时变量temp为满足题意的数对第二个元素。
为什么可以贪心
按数对第二个元素排序后，可以保证每步都是缓慢增加的 ，若第二个元素较大的排在前面，则一定会有可行结果被丢弃，因此可以贪心
代码
Arrays.sort(pairs, (a , b) -> a[1] - b[1]);
int temp = pairs[0][1];
int ans = 1;
for(int i=1; i<pairs.length; i++){
if(pairs[i][0] > temp){
ans++;
temp = pairs[i][1];
}
}
return ans;
方法二（可能超时 不推荐）：动态规划
动态规划法思想： 将pairs按数对中第一个元素排序，定义一数组 dp[len]，存储第i 个元素具有的最长满足题意数对长度， 每次循环， 遍历前 i 个元素， 找到第j 个数对中第二个数小于第 i 个数对中的第一个数， 更新 dp[i] 为 Math.max(dp[i], dp[j]+1)
int len = pairs.length;
int dp[] = new int[len];
Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
Arrays.fill(dp, 1);
for(int i=0; i<len; i++){
for(int j=0; j<i; j++){
if(pairs[i][0] > pairs[j][1]){
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
}
return dp[len - 1];