最长数对链：先理解动态规划，再看为什么选最早结束的数对

力扣 646给出若干 [left,right]每对都满足 left right。若前一对的右端点严格小于后一对的左端点就能接起来。允许重新排列和跳过数对求链的最大长度。例如 [1,2] 不能接 [2,3]因为 2 2 不成立[1,2] - [3,4] 才合法。我原来想到最长递增子序列dp[i] 表示以第 i 个数对结尾的最长链。这个方向正确但本题允许重排必须先说明排序为什么能帮助填表不能把输入顺序当作 LIS 的固定顺序。1. 为什么先按左端点排序如果 [a,b] 可以接到 [c,d] 前面就有 a b c d前一对的左端点也一定更小。因此按左端点升序后所有可能接在第 i 对前面的数对都在它前面。但左端点更小只是候选不代表一定能接还得检查它的右端点是否严格小于当前左端点。原图用 [1,2]、[4,5]、[7,8] 写出 dp 为 1、2、3。下面补一个有干扰项的例子看看为什么不能只选紧挨着的上一对。2. 把状态真的填一遍按左端点排序后的输入[1,10] [2,3] [4,5] [6,7]i当前数对能接在前面的数对dp[i]0[1,10]没有11[2,3]没有10不小于212[4,5][2,3]23[6,7][2,3]、[4,5]3最长链是 [2,3] - [4,5] - [6,7]开头那对虽然开始早却占了很大的范围。转移是从所有满足 pairs[j][1] pairs[i][0] 的 j 中选 dp[j]1 的最大值没有前驱时保持 1。最终返回整个 dp 的最大值不能假设最后一对一定是最优链的结尾。3. Java 动态规划实现import java.util.Arrays; class DpSolution { public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, (a, b) - Integer.compare(a[0], b[0])); int n pairs.length; int[] dp new int[n]; Arrays.fill(dp, 1); int answer 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (pairs[j][1] pairs[i][0]) { dp[i] Math.max(dp[i], dp[j] 1); } } answer Math.max(answer, dp[i]); } return answer; } }若提交平台只接受 Solution将类名改为 Solution 即可。用 Integer.compare 避免把减法比较器当成通用写法在原题有限端点范围内原减法并不会溢出不把这次调整说成原题运行错误。DP 为 O(n²) 时间dp 数组 O(n) 空间对象数组排序也可能使用额外空间。本实现原地改变数对的外层顺序需要保留输入时先复制外层数组。4. 能不能不试所有前驱当前已经有一条链下一个能接的数对中我们希望给未来留下尽量多的空间。关键不在它开始多早而在它结束多早。看前面的干扰例子先选 [1,10] 就没法接后面的短对先选 [2,3] 则能继续接 [4,5]、[6,7]。因此改为按右端点升序遇到第一个能接上的就选然后继续。5. 为什么贪心不是碰巧设一个最优方案的下一对是 P而当前能接的数对中结束最早的是 G。G 的结束点不晚于 P且两者都能接上已有前缀。把方案里的 P 换成 GP 后面原来能接的数对也一定能接在结束更早的 G 后面。长度没有减少给后续留下的空间没有变小。原最优方案已有前缀 - P - 后续 替换之后 已有前缀 - G - 同样的后续 G结束不晚于P所以总存在一个同样长的最优方案采用这次贪心选择。对剩余部分继续同样做就能得到最长链。这比只说“每次选最小所以整体最优”多了关键一步证明替换不会损坏后续。import java.util.Arrays; class GreedySolution { public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, (a, b) - Integer.compare(a[1], b[1])); int answer 0; int end 0; for (int[] pair : pairs) { if (answer 0 || end pair[0]) { answer; end pair[1]; } } return answer; } }第一对无需和虚构的初始端点比较answer 0 处理这个情况。扫描 O(n)排序 O(n log n)总体 O(n log n)。扫描本身常数空间但 Java 对象数组排序可能用 O(n) 辅助空间不能把整个方法直接称为 O(1) 空间。6. 边界与独立验证本次实际编译运行两段 Java。短数组用第三个程序穷举不排序试每个尚未使用、能接在当前链后面的数对找最大长度。它不使用 DP 转移表也不使用最早结束策略。两种解法分别使用独立输入副本避免第一次排序掩盖第二次的输入问题。另检查打乱输入顺序后答案不变并加入重复数对、负端点、相等边界与长范围干扰项。输入答案检查什么[1,2]、[2,3]1必须严格小于不是小于等于[1,2]、[1,2]1重复项不会凭空延长链[1,10]、[2,3]、[4,5]、[6,7]3不能按开始最早贪心[-5,-4]、[-3,-2]、[-1,0]3负数也适用同时故意把贪心里的 改成 以及把右端点排序误写成左端点排序测试器必须找出错误。随机对拍只能提高信心不能代替前面的交换理由。这道题的两条路线可以一起保留DP 帮我明确“以谁结尾”的状态贪心则进一步抓住“结束越早后面越自由”的结构。不是所有 DP 都能这样优化而是这道题的替换性质允许我们省去枚举前驱。