V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
spencerqiu
V2EX  ›  问与答

最长非降子序列问题的动态转移方程没看懂

  •  
  •   spencerqiu · 2014-10-26 21:43:27 +08:00 via iPad · 2655 次点击
    这是一个创建于 3687 天前的主题,其中的信息可能已经有所发展或是发生改变。


    这边 f(i) 直接就等于之前所有结果中的最大结果 +1 了,感觉怪怪的。

    比如第九次,加入的是 16 不能把它放进去,这个方程又是个什么意思呢?
    7 条回复    2014-10-27 01:55:14 +08:00
    mousepotato
        1
    mousepotato  
       2014-10-26 22:56:16 +08:00 via iPhone
    请问lz这本书名,多谢!
    spencerqiu
        2
    spencerqiu  
    OP
       2014-10-26 23:10:30 +08:00 via iPad
    @mousepotato
    高中生用的教材,不是那种应付面试的哦。
    zhsso
        3
    zhsso  
       2014-10-26 23:17:25 +08:00   ❤️ 1
    这边 f(i) 直接就等于之前所有结果中的最大结果 +1 了,感觉怪怪的。
    这句话错的,有限定条件,应该是等于之前a[i] > (>=?) a[j]的最大结果+1
    应付面试的题目也可以提高算法的....
    windywinter
        4
    windywinter  
       2014-10-26 23:20:29 +08:00   ❤️ 1
    转移方程上少写了个条件
    zhsso
        5
    zhsso  
       2014-10-26 23:24:22 +08:00   ❤️ 1
    前面还有个max....其实就是判断加入第i个数后,能达到的最长长度,要么为f(i-1),要么为f(j)+1(i<j && a[i] > a[j])的最大值,哪个大就哪个
    llbbzh
        6
    llbbzh  
       2014-10-27 00:49:29 +08:00 via iPhone
    建议看看这个问题O(nlgn)的算法
    heliumhgy
        7
    heliumhgy  
       2014-10-27 01:55:14 +08:00   ❤️ 1
    @spencerqiu 其实说白了就是在一个数组f中第i个元素(f[i])中保存原序列a中前i个元素的最长非降子序列的长度,当扩展到第i+1个元素的时候,只需要在前i个元素中找到符合非降的元素j(符合条件a[j]<=a[i]),那么f[j]+1就是一个非降子序列的长度,就可以赋值给f[i+1],用max选出了最长的那个子序列的长度并存起来就好了,一直搜索下去,f[n]就是解了。。。用另外一个数组你还能知道这个最长的子序列到底是什么。。。
    如果看懂了就点个感谢还我金币!!!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1991 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:15 · PVG 00:15 · LAX 08:15 · JFK 11:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.