[数据结构与算法]【排序25：俄罗斯套娃信封问题】（动态规划 / 二维最长公共子序列 / 基于二分查找的动态规划）

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

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

注意：不允许旋转信封。

?
示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

【解题思路】刚开始使用贪心算法，通过了部分测试样例，在遇到

int[][] envelopes = new int[][] {{2,100},{3,200},{4,300},{5,500},{5,400},{5,250},{6,370},{6,360},{7,380}};

这样的测试样例，发现贪心算法无法解决该问题，应该使用动态规划。

1、贪心算法

package test;

import java.util.*;
import java.util.stream.Collectors;
import java.lang.System;

import static java.lang.System.arraycopy;

public class test {
    public static void main(String[] args) {
        int[][] envelopes = new int[][] {{2,100},{3,200},{4,300},{5,500},{5,400},{5,250},{6,370},{6,360},{7,380}};
        Arrays.sort(envelopes,new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return a[1]-b[1];
                else return a[0]-b[0];
            }
        });

        int ans = 0;
        int curX = 0;
        int curY = 0;
        for(int i = 0; i < envelopes.length; i++)
        {
            if(curX < envelopes[i][0] && curY < envelopes[i][1])
            {
                ans++;
                curX = envelopes[i][0];
                curY = envelopes[i][1];
            }
        }
        System.out.print(ans);

    }
}

2、动态规划

设 f[i]?表示 h?的前 i 个元素可以组成的最长严格递增子序列的长度，并且我们必须选择第 i?个元素 hi?。在进行状态转移时，我们可以考虑倒数第二个选择的元素 hj，必须满足 hj < hi, j<i。但可惜，该方法超出时间限制。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes,new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return b[1]-a[1];
                else return a[0]-b[0];
            }
        });

        int[] f = new int[envelopes.length];
        int ans = 1;
        Arrays.fill(f, 1);
        for(int i = 1; i < envelopes.length; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(envelopes[i][1] > envelopes[j][1])
                {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            ans = Math.max(f[i], ans);
        }

        return ans;
    }
}

3、基于二分法的动态规划

使用f[i]记录最长公共子序列的值，下一个数如果大于当前最大值，则插入，否则插入合适的位置。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) {
            return 0;
        }
        
        int n = envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0]) {
                    return e1[0] - e2[0];
                } else {
                    return e2[1] - e1[1];
                }
            }
        });

        List<Integer> f = new ArrayList<Integer>();
        f.add(envelopes[0][1]);
        for (int i = 1; i < envelopes.length; ++i) {
            int num = envelopes[i][1];
            if (num > f.get(f.size() - 1)) {
                f.add(num);
            } else {
                int index = binarySearch(f, num);
                f.set(index, num);
            }
        }
        return f.size();
    }

    public int binarySearch(List<Integer> f, int target) {
        int low = 0, high = f.size() - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (f.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}