V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
kuanng
V2EX  ›  程序员

你们在工作中,动态规划用的多吗?

  •  
  •   kuanng · 2020-04-22 11:38:49 +08:00 · 7595 次点击
    这是一个创建于 1436 天前的主题,其中的信息可能已经有所发展或是发生改变。

    除了刷题,工作当中用到动态规划的情况多吗?

    43 条回复    2020-04-23 09:15:04 +08:00
    yazoox
        1
    yazoox  
       2020-04-22 11:43:53 +08:00
    面试被面的多......
    xFan
        2
    xFan  
       2020-04-22 11:46:17 +08:00
    用过一次 物流项目 装货时候
    lithbitren
        3
    lithbitren  
       2020-04-22 11:50:33 +08:00
    没用过,能和算法沾边的都是各种数据结构的相关算法,比如搜索或遍历之类,有个别数据结构的算法勉强算是基于 DP 的,即有状态的记忆化搜索,纯 DP 的场景没见过。

    可能涉及到调度或规划的项目会用到吧。。
    salamanderMH
        4
    salamanderMH  
       2020-04-22 11:53:41 +08:00
    刷题用得多
    newtype0092
        5
    newtype0092  
       2020-04-22 11:55:02 +08:00
    游戏开发应该用的到
    across
        6
    across  
       2020-04-22 11:57:07 +08:00
    @newtype0092
    没有啊。想了一圈也没想到对应的场景。
    是三消那种特殊的解谜游戏才用到吧?
    lechain
        7
    lechain  
       2020-04-22 12:13:59 +08:00 via Android   ❤️ 8
    昨天发现的,工作快两年了连递归都没用过,别说动态规划了……
    jmc891205
        8
    jmc891205  
       2020-04-22 12:39:29 +08:00
    不多 不过用得到
    前几天写了一段 code 还用到了
    bobuick
        9
    bobuick  
       2020-04-22 12:42:21 +08:00
    做游戏,特别是深度一点的 RPG,非回合制游戏这些会比较容易遇到,还有些其他的算法也能遇到。不过也基本上引擎这类的上面,业务逻辑是没什么机会遇到的
    sadfQED2
        10
    sadfQED2  
       2020-04-22 12:44:25 +08:00 via Android
    Cudr 仔表示从来没用过
    wangyzj
        11
    wangyzj  
       2020-04-22 12:47:38 +08:00
    递归几乎都没有
    别说算法了
    dilu
        12
    dilu  
       2020-04-22 12:48:29 +08:00   ❤️ 1
    工作中 99%是 for 跟 if
    xizismile
        13
    xizismile  
       2020-04-22 14:25:26 +08:00 via Android
    组装父子层级数据的时候,用过递归
    llb123
        14
    llb123  
       2020-04-22 14:53:48 +08:00
    递归都没用过有点夸张了吧
    myd
        15
    myd  
       2020-04-22 14:54:36 +08:00
    没用过
    Liutos
        16
    Liutos  
       2020-04-22 14:56:57 +08:00
    只有做题的时候会用到
    thedrwu
        17
    thedrwu  
       2020-04-22 14:58:25 +08:00 via Android
    用过
    luckyrayyy
        18
    luckyrayyy  
       2020-04-22 15:00:54 +08:00
    CRUD boy 平时就用用排序和查找啊,但是这俩都有非常好用的现成的实现。
    susecjh
        19
    susecjh  
       2020-04-22 15:12:59 +08:00
    没有
    ZehaiZhang
        20
    ZehaiZhang  
       2020-04-22 15:42:33 +08:00
    用过递归,二叉树
    LeeSeoung
        21
    LeeSeoung  
       2020-04-22 15:45:03 +08:00
    = =用动规的话 后面看代码的人改起来会不会骂人。。
    zypy333
        22
    zypy333  
       2020-04-22 15:48:57 +08:00
    @ZehaiZhang 二叉是什么场景呢
    BiteTheDust
        23
    BiteTheDust  
       2020-04-22 15:56:35 +08:00
    可以用动态规划做一个井字棋 AI
    lithbitren
        24
    lithbitren  
       2020-04-22 16:03:12 +08:00
    @LeeSeoung 没见过,不知道真实的动归生产环境是怎样的,不过估计用动归应该都是准算法场景了吧,除非是文档齐全、状态转移明确的动归,否则只能打补丁或重写了,如果找不到原作者的话。
    newtype0092
        25
    newtype0092  
       2020-04-22 16:47:57 +08:00
    @across 假如做一个一键更换最优装备搭配的功能,如果只是简单根据装备的评分排序的话,对有“套装”、“羁绊”等联动效果的情况就没法处理。
    最近玩骑砍 2,NPC 商队进程交易,所有商品价格都是动态的,甚至包括马匹,而马匹又影响负重,不知道有没有用 DP,这种如果不用的话 AI 会比较蠢。
    反正一般贪心求出最优解的话最先想到的可能就是 DP 了,而游戏不就是各种花式求最优解的大场景么。
    nianyu
        26
    nianyu  
       2020-04-22 16:52:10 +08:00
    没用过
    zhch602
        27
    zhch602  
       2020-04-22 17:13:19 +08:00
    @llb123 #14 用递归不怕影响效率么?
    wizardoz
        28
    wizardoz  
       2020-04-22 17:22:19 +08:00
    @zhch602 递归不会影响效率
    zhch602
        29
    zhch602  
       2020-04-22 17:25:39 +08:00   ❤️ 1
    @wizardoz #27 你在搞笑么,递归比循环效率低很多,还容易引起 stack overflow
    xingheng
        30
    xingheng  
       2020-04-22 17:29:43 +08:00
    8 年开发,iOS,用过一些递归,动态规划是真没有。

    @zhch602 不会影响效率,大都是因为业务层数据并没有那么大的深度。
    edussx
        31
    edussx  
       2020-04-22 17:29:44 +08:00
    递归不好 debug,非尾递归还容易爆栈。生产环境的代码在保证性能的前提下最重要的是可维护性、可读性、可靠性,其他都是虚的
    CoderGeek
        32
    CoderGeek  
       2020-04-22 17:36:18 +08:00
    一点递归 其它都是自己写着玩的
    kaedea
        33
    kaedea  
       2020-04-22 17:37:38 +08:00 via Android   ❤️ 1
    代码里用得不多,多个需求并行开发经常被别人打断,因此在工作管理上动态规划实践得比较多。
    cuzfinal
        34
    cuzfinal  
       2020-04-22 17:43:35 +08:00
    完全没有
    guanyinli
        35
    guanyinli  
       2020-04-22 19:17:48 +08:00
    暴力能解决的事那就不是事
    Anarchy
        36
    Anarchy  
       2020-04-22 19:34:52 +08:00
    很少能直接用到,很多复杂的逻辑都有轮子用了。
    111qqz
        37
    111qqz  
       2020-04-22 19:37:31 +08:00
    从没用过,见过一次,忘记什么场景了。 图相关的算法用的多一些,比如二分图最佳匹配啥的...
    paoqi2048
        38
    paoqi2048  
       2020-04-22 20:27:58 +08:00
    游戏开发会有一些
    pisc
        39
    pisc  
       2020-04-22 20:43:52 +08:00 via Android
    @zhch602 不是所有的语言递归都会 stack overflow,也不是所有的递归就会比等价的循环效率低,在靠谱一点的编译器都会做分析优化,比如尾递归就会直接优化,不会重复 push 到栈中。再说了,不能用尾递归解决的问题都依赖上下文,用循环实现还需要自己手动模拟栈,直接用递归反而简单。
    optional
        40
    optional  
       2020-04-22 20:55:53 +08:00 via iPhone
    面试也是工作的一部分。
    EatMi
        41
    EatMi  
       2020-04-22 21:01:25 +08:00
    物流专业在读大学生, 考研的运筹学,一道大题, 动态规划....................
    zhw2590582
        42
    zhw2590582  
       2020-04-22 22:13:00 +08:00
    楼上说递归都没用过,你们都不写数据处理逻辑了吗
    babyrjw
        43
    babyrjw  
       2020-04-23 09:15:04 +08:00
    唯一用过的一次是做费用成本优化,跟明星解了一个一元二次方程就变成学霸一样的感觉
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1384 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 17:32 · PVG 01:32 · LAX 10:32 · JFK 13:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.