646. 最长数对链（动态规划）

╰+攻爆jí腚メ 2023-10-05 18:23 5阅读 0赞

#### 646. 最长数对链 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

![在这里插入图片描述][20210125190033304.png]

提示：

*  给出数对的个数在 \[1, 1000\] 范围内。

## 解题思路 ##

这题其实借用了 [354.俄罗斯套娃信封问题][354.]的思想。我们需要对这个二维数组的开始值进行升序排序，如果遇到相同的，就按照结束值进行降序排序，然后就得到了一个排序后的数组。

我们这里就可以用[300.最长递增子序列][300.]的方法来求出结果了。

需要注意的是if判断那一块：要注意用前一个的结束和后一个的开始去进行比较。因为这个单独抽离成一个一维数组比较麻烦，所以直接在这里用这种方式进行比较。

/*用nums当前的开始去比较nums之前的 结束 。
    	[[1,2],[3,4]] 这就相当于用3去和2比较
    */
    if (nums[j][1] < nums[i][0]) {
        
         dp[i] = Math.max(dp[i], dp[j] + 1);
         }

## 代码 ##

class Solution {
        
            public int findLongestChain(int[][] pairs) {
        
            int N = pairs.length;
            if (N == 0) {
        
                return 0;
            }
    
            Arrays.sort(pairs, new Comparator<int[]>() {
        
                //按照每个区间的开始进行升序排列，若开始一样，则按结束降序排列
                public int compare(int[] a, int[] b) {
        
                    /*
                        a[0]、b[0]分别代表前一个、后一个数组的开始
                        a[1]、b[1]分别代表前一个、后一个数组的结束
                    */
                    return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
                }
            });
    
            return lengthOfLIS(pairs);
    
        }
    
    
        //用来求最长递增子序列。这里稍微修改一下作为辅助方法
        public int lengthOfLIS(int[][] nums) {
        
    
            if (nums.length == 0) {
        
                return 0;
            }
            int N = nums.length;
            //dp[i]存放的是：以nums[i]结尾的最长递增子序列的长度
            int[] dp = new int[N];
    
    
            //base case：将dp[]都初始化为1
            Arrays.fill(dp, 1);
    
            for (int i = 0; i < N; i++) {
        //i=N-1就是dp[]的最后一个元素了，原为dp[]的长度和nums[]的相同
                for (int j = 0; j < i; j++) {
        
                    /*用nums当前的开始去比较nums之前的 结束 
                        假设有[[1,2],[3,4]] 这就相当于用3去和2比较
                     */
                    if (nums[j][1] < nums[i][0]) {
        
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
    
            int res = 0;
            //来遍历一次经过整理的dp[]，找出最大值
            for (int i = 0; i < dp.length; i++) {
        
                res = Math.max(res, dp[i]);
            }
    
            return res;
    
        }
    }

[20210125190033304.png]: https://img-blog.csdnimg.cn/20210125190033304.png
[354.]: https://leetcode-cn.com/problems/russian-doll-envelopes/
[300.]: https://leetcode-cn.com/problems/longest-increasing-subsequence/