思路
如果想让信封A完全放入信封B,则A的宽和高必须均小于B的宽和高
为了能尽可能的多放,需要挑选次大的信封作为当前信封的容器
如果
按照宽度进行升序排列且宽度不存在等长的情况下,则只需要考虑挑选高度次大的即可
则
求最大套娃其实就是挑选出所有高度递增的区间,取最大的哪一个
则在高度上的伪代码如下
但是现在的问题是宽度可能相等
此时基于原有的分析,针对数组[[1,2],[1,3],[1,4]]得出的结论是三个,是不对的
故需要考虑对宽度也做一定调整
根据上述代码,在不考虑宽度的情况下,发现num[j]<num[i]即作为更长结果记录下来了
则
如果对[1,2]和[1,3]位置互换,则不满足记录条件,同时由于是等宽的,也不影响排序的结果
故
状态定义
dp[i]表示以i结尾的最长上升序列的长度
转移方程
dp[i] = max(dp[0]......dp[i-1])+1,其中隐含条件为hi-1<hi
实现
网友评论