354. 俄罗斯套娃信封问题（动态规划）

354. 俄罗斯套娃信封问题

• 题目
• 解题思路
• 代码

题目

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:

• 不允许旋转信封。

解题思路

因为我们写过一维的LIS算法。所以我们想办法往一维数组上面靠。
我们把宽度W进行升序排序，然后遇到W相同的情况就按照高度H进行降序排序。最后把排序后的H作为一个一维数组，那么就可以用标准的LIS算法去解决这个一维数组。得到的结果就是我们要的结果。

关键在于,对于宽度w相同的数对,要对其高度h进行降序排序。
因为两个W相同的信封不能相互包含,W相同时将h逆序排序,则这些逆序h中最
多只会有一个被选入递增子序列,保证了最终的信封序列中不会出现w相同的情况。

代码

class Solution {

    public int maxEnvelopes(int[][] envelopes) {

        int N = envelopes.length;
        if (N == 0) {
            return 0;
        }

        Arrays.sort(envelopes, 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];
            }
        });
            int[] target=new int[N];

            for(int i=0;i<N;i++){
                target[i]=envelopes[i][1];//把排序后的高度单独提取出来
            }

        return lengthOfLIS(target);

    }


    //用来求最长递增子序列。这里稍微修改一下作为辅助方法
    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++) {
                if (nums[j] < nums[i]) {
                    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;

    }
    
}