问题描述

俄罗斯套娃信封问题是一个经典的动态规划问题，题目要求是给出一组信封的长（width）和宽（height），求最多可以套入多少个信封。

例如，给定信封的数组为[(5,4),(6,7),(2,3),(6,5)]，则最多可以套入3个信封，其中一个有效的套娃信封序列为[(2,3),(5,4),(6,7)]。

解题思路

本题可以通过动态规划的思路来解决。首先，我们需要将信封按照长或者宽进行排序，以方便后续的比较。然后我们定义一个dp数组，dp[i]表示到第i个信封为止，最多可以套入多少个信封。

接下来，我们遍历每一个信封，对于当前信封i，我们遍历它之前的每一个信封j，如果当前信封i的长和宽都大于信封j的长和宽，那么我们可以将信封i套入信封j中。对于每一个可以套入信封i的信封j，我们更新dp[i]的值为dp[j]+1，表示到第i个信封为止，最多可以套入dp[j]+1个信封。

最后，我们遍历dp数组，找到其中的最大值，即为最多可以套入的信封数量。

代码实现


def maxEnvelopes(envelopes):
    if len(envelopes) < 2:
        return len(envelopes)
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    dp = [1] * len(envelopes)
    for i in range(1, len(envelopes)):
        for j in range(i):
            if envelopes[i][1] > envelopes[j][1]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

代码解析

首先，我们判断数组长度是否小于2，如果是，则直接返回数组长度。

接下来，我们对信封数组进行排序，按照长升序，如果长相同则按照宽降序排序。

然后，我们初始化dp数组，长度为信封数组的长度，并且所有元素初始化为1。

遍历信封数组，对于每一个信封i，再遍历它之前的每一个信封j。如果当前信封i的宽大于信封j的宽，那么可以将信封i套入信封j中，并更新dp[i]的值为dp[j]+1。

最后，遍历dp数组，找到其中的最大值，即为最多可以套入的信封数量。

复杂度分析

时间复杂度：排序的时间复杂度为O(nlogn)，遍历的时间复杂度为O(n^2)，总的时间复杂度为O(n^2)。

空间复杂度：使用了一个dp数组，所以空间复杂度为O(n)。