讨论/《动态规划精讲(一)》 - 俄罗斯套娃信封问题/
《动态规划精讲(一)》 - 俄罗斯套娃信封问题
共 14 个回复

方法:排序 + 最长递增子序列

该问题为最长递增子序列的二维问题。

我们要找到最长的序列,且满足 seq[i+1] 中的元素大于 seq[i] 中的元素。

该问题是输入是按任意顺序排列的——我们不能直接套用标准的 LIS 算法,需要先对数据进行排序。我们如何对数据进行排序,以便我们的 LIS 算法总能找到最佳答案?

我们可以在这里找到最长递增子序列的解决方法。如果您不熟悉该算法,请先理解该算法,因为它是解决此问题的前提条件。

算法:
假设我们知道了信封套娃顺序,那么从里向外的顺序必须是按 w 升序排序的子序列。

在对信封按 w 进行排序以后,我们可以找到 h 上最长递增子序列的长度。、

我们考虑输入 [[1,3],[1,4],[1,5],[2,3]],如果我们直接对 h 进行 LIS 算法,我们将会得到 [3,4,5],显然这不是我们想要的答案,因为 w 相同的信封是不能够套娃的。

为了解决这个问题。我们可以按 w 进行升序排序,若 w 相同则按 h 降序排序。则上述输入排序后为 [[1,5],[1,4],[1,3],[2,3]],再对 h 进行 LIS 算法可以得到 [5],长度为 1,是正确的答案。这个例子可能不明显。

我们将输入改为 [[1,5],[1,4],[1,2],[2,3]]。则提取 h[5,4,2,3]。我们对 h 进行 LIS 算法将得到 [2,3],是正确的答案。

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, arr: List[List[int]]) -> int:
        # sort increasing in first dimension and decreasing on second
        arr.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            dp = []
            for i in range(len(nums)):
                idx = bisect_left(dp, nums[i])
                if idx == len(dp):
                    dp.append(nums[i])
                else:
                    dp[idx] = nums[i]
            return len(dp)
        # extract the second dimension and run the LIS
        return lis([i[1] for i in arr])
class Solution {

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }

    public int maxEnvelopes(int[][] envelopes) {
        // sort on increasing in first dimension and decreasing in second
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] arr1, int[] arr2) {
                if (arr1[0] == arr2[0]) {
                    return arr2[1] - arr1[1];
                } else {
                    return arr1[0] - arr2[0];
                }
           }
        });
        // extract the second dimension and run LIS
        int[] secondDim = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; ++i) secondDim[i] = envelopes[i][1];
        return lengthOfLIS(secondDim);
    }
}

复杂度分析

  • 时间复杂度:O(NlogN)O(N \log N)。其中 NN 是输入数组的长度。排序和 LIS 算法都是 O(NlogN)O(N \log N)
  • 空间复杂度:O(N)O(N)lis 函数需要一个数组 dp,它的大小可达 NN。另外,我们使用的排序算法也可能需要额外的空间。
7

允许旋转信封的话思路也一样的,都是先排序,只不过要以每个信封最短的边进行排序,做法还是一样的

2

这里给出的不允许旋转信封, 如果可以旋转信封要怎么做?

2
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // 最优解:最多个连续上升的信封
        // 子问题:连续上升的信封

        if(envelopes == null || envelopes.length == 0) {
            return 0;
        }
        int length = envelopes.length;
        if(length == 1) {
            return 1;
        }

        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] a1, int[] a2) {
                return a1[0]-a2[0];
            }
        });
        
        int[] dp = new int[length];
        Arrays.fill(dp, 0);
        int max = 0;
        for(int i=0;i<length;i++) {
            max = Math.max(f(envelopes, i, dp), max);
        }
        return max;
    }

    private int f(int[][] envelopes, int i, int[] dp) {
        if(dp[i] != 0) {
            return dp[i];
        }
        int max = 0;
        for(int j=0;j<i;j++) {
            if(envelopes[j][0] < envelopes[i][0] &&
               envelopes[j][1] < envelopes[i][1])
            {
                max = Math.max(f(envelopes, j, dp), max);
            }
        }
        dp[i] = max+1;
        return dp[i];
    }

}

贪心+二分
贪心:求最长上升子序列时,如果长度相同的情况,最后的数字越小,后边可以拼的数字可以越多。
dp[i]表示“长度为(i+1) && 第i+1个数字为dp[i]的子序列”

int[] dp = new int[nums.length];

总感觉这个与dp好像关系不大。更像是在维护一个lis 最终lis的实际元素个数就是答案

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>o2[0]){
                    return 1;
                }else if(o1[0]<o2[0]){
                    return -1;
                }else if(o1[1]>o2[1]){
                    return 1;
                }else if(o1[1]<o2[1]){
                    return -1;
                }else{
                    return 0;
                }
            }
        });
        if(envelopes.length==1) return 1;
        int[] dp=new int[envelopes.length];
        Arrays.fill(dp,1);
        int maxans=1;
        for(int i=1;i<envelopes.length;i++){
            for(int j=0;j<i;j++){
                if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            maxans=Math.max(maxans,dp[i]);
        }
        return maxans;
    }
}

Arrays.binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
a:要搜索的数组

fromIndex:指定范围的开始处索引(包含)

toIndex:指定范围的结束处索引(不包含)

key:要搜索的值

如果要搜索的元素key在指定的范围内,则返回搜索值的索引;否则返回-1或的插入点值(插入点)。
真好,不用自己写二分法求解了,二分法的写法,在最长上升子序列里有

不需要去重,因为如果h2比h1高,那么w2绝对比w1大,因为w相同的情况下,h2会比h1小或者相同。
h2,h1指的是下标,h1<h2

一样的吧,比如永远将信封最短的边作为宽就行了