DP--俄罗斯套娃信封（线性-单串）

目录

题号

思路

    如果想让信封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

实现