给你一个二元信息组envelopes 其中 envelopesi = wi hi 表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候这个信封就可以放进另一个信封里如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组俄罗斯套娃信封即可以把一个信封放到另一个信封里面。注意:不允许旋转信封。【输入】:第一行为一个正整数nINT范围内代表信封总数接下来一行包含2n个正整数INT
思路:首先按照宽度从小到大排序,如果宽度相同则按照高度从大到小排序。然后就转化为了求高度的最长上升子序列(LIS)问题。可以使用动态规划解决。定义dp[i]表示以第i个信封为结尾的最长上升子序列长度,初始化为1。对于每个i,遍历0~i-1的所有j,如果envelopes[j]可以放入envelopes[i]中,则更新dp[i]=max(dp[i],dp[j]+1)。最终的答案为dp数组中的最大值。
时间复杂度:O(n^2)
原文地址: https://www.cveoy.top/t/topic/ht7h 著作权归作者所有。请勿转载和采集!