0%

leetcode.354. 俄罗斯套娃信封问题

leetcode.354. 俄罗斯套娃信封问题

问题描述


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

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


动态规划

思路分析


dp[i] 代表以i为结尾的最长上升子序列


代码实现

源码

LIS算法

思路分析


tails[i] 代表最长上升子序列长度为i时,结尾元素的


代码实现

源码