给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w h) 出现.当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样.
请计算最多能有多少个信封能组成一组"俄罗斯套娃"信封(即可以把一个信封放到另一个信封里面).
俄罗斯套娃信封是道困难题,其前置题目是300. 最长递增子序列,所以先以这个前置题目入手,其关键是知道状态转移方程.
问题描述: 给定一个无序的整数数组,找到其中最长上升子序列(LIS)的长度.
问题的关键是状态转移方程为 : dp[i]=max(dp[j])+1其中0≤j<i且num[j]<num[i].
需要注意的是这里的状态dp[j]指的是以第j个数字结尾的子序列(注意是子序列以num[i]结尾)的最长的长度.
找到同时满足envelopes[0]递增,envelopes[1]也递增的序列.
由于envelopes[0]递增(这里先不考虑envelopes[0]相等的情况),只需要考虑envelopes[1]的最长递增子序列就可以了.
上面的题解链接有图解.这里的关键是dp[i]用来存放长度为i的子序列末尾的最小的数字.