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

646. 最长数对链

• 题目
• 解题思路
• 代码

题目

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

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

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

提示：

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

解题思路

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

我们这里就可以用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;

    }
}