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

请教下,动态规划有什么分析问题的方式吗?

  •  
  •   ukipoi · 2021-01-08 16:28:53 +08:00 · 942 次点击
    这是一个创建于 1176 天前的主题,其中的信息可能已经有所发展或是发生改变。

    就是我在知道一道题目可以用动态规划解决的前提下,还是想不出。 也做了十几题标签是动态规划的题目了,但是用动态规划解出来了一半都不到。

    比如 leetcode 的第 44 题
    https://gist.github.com/ukipoi/8b42cd4e9cd0607d616452cd4bf65987
    第 5 题
    https://gist.github.com/ukipoi/c58c7c41196e4c755ec0a3dbd982ab3a

    如果是爬楼梯这样的题目,我可以想出用动态规划解决的方式,但是复杂一些就想不到了

    3 条回复    2021-01-08 16:54:08 +08:00
    lithbitren
        1
    lithbitren  
       2021-01-08 16:37:07 +08:00
    没有,没见过的 hard 题型,除了少数,大概率面试也做不出来,只能多做多背
    easonHHH
        2
    easonHHH  
       2021-01-08 16:52:13 +08:00
    我个人觉得,就是怎么样把状态转移方程写出来,然后怎么存储备忘录来优化空间复杂度和时间复杂度
    最近在看一个大佬的博客
    https://labuladong.gitee.io/algo/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E8%AF%A6%E8%A7%A3%E8%BF%9B%E9%98%B6.html
    ai277014717
        3
    ai277014717  
       2021-01-08 16:54:08 +08:00
    动态规划的思想是找到合适的子问题。用子问题作出等式。爬楼梯是最简单的斐波纳切公式。多刷题总结公式类型。可以往里套。复杂的题目可能会涉及到微分。这种是真难做。数学早忘光了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3205 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 10:52 · PVG 18:52 · LAX 03:52 · JFK 06:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.