美文网首页
DP--俄罗斯套娃信封(线性-单串)

DP--俄罗斯套娃信封(线性-单串)

作者: 习惯水文的前端苏 | 来源:发表于2022-02-14 10:00 被阅读0次

    \bullet 目录

    \bullet 题号

    \bullet 思路

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

    \bullet 实现

    相关文章

      网友评论

          本文标题:DP--俄罗斯套娃信封(线性-单串)

          本文链接:https://www.haomeiwen.com/subject/vdpwkrtx.html