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

理解不了动态规划会对后端程序员职业发展有哪些影响?

  •  
  •   zhoudaiyu · 2021-05-17 19:06:14 +08:00 · 4892 次点击
    这是一个创建于 1287 天前的主题,其中的信息可能已经有所发展或是发生改变。

    普通后端程序员,非算法岗

    33 条回复    2021-05-19 18:56:21 +08:00
    ysn2233
        1
    ysn2233  
       2021-05-17 19:07:35 +08:00
    没影响
    werls
        2
    werls  
       2021-05-17 19:07:41 +08:00   ❤️ 1
    平时就 crud 。有什么影响?
    secsilm
        3
    secsilm  
       2021-05-17 19:11:02 +08:00 via Android
    这和是否算法岗( AI )无关吧,
    index90
        4
    index90  
       2021-05-17 19:13:12 +08:00
    被面试虐了?用来在众多合适的候选人中,继续筛选用的。
    LeeReamond
        5
    LeeReamond  
       2021-05-17 19:29:45 +08:00 via Android
    如果你指不能设计 dp 算法的话,没什么影响,应该大多数人不具备这个能力。如果你指不能理解个别算法的话,应该没什么影响。如果你无法照本宣科实现?那似乎发展会非常受限?
    WhereverYouGo
        6
    WhereverYouGo  
       2021-05-17 19:52:20 +08:00
    有概率无法通过字节、阿里、腾讯 or 其他公司的某一轮面试😼
    Sasasu
        7
    Sasasu  
       2021-05-17 20:24:13 +08:00   ❤️ 1
    你先撇开状态转移方程那一堆。

    假设你需要实现一个阶乘 API,输入一个数,输出这个数的阶乘.

    然后,假设你的机器硬件层面运算 * 特别慢,你给 f(x) 加上了个缓存。
    每次先看看缓存里有没有结果,有就直接返回。

    这就是一维动态规划了,开一个数组作为缓存,T[n] 中 n 就是输入 T[n] 就是结果,转移方程:
    f(x) = f(x-1) * 1, f(0) = 1

    这和你无脑加缓存有啥区别
    powerman
        8
    powerman  
       2021-05-17 20:31:38 +08:00   ❤️ 1
    @Sasasu 这只是动态规划的另外一种实现方式,实际上递归调用是与迭代递推是等价的,而且前者比后者更容易理解与实现,

    DP 的难点不是编程,难点是推导出递推方程式,而且推导递推公式非常难,而且不是那么显然,而用递归缓存子问题的结果是比较容易理解的方式,实现起来比较容易,维护比较简单,从工程的角度来讲,迭代的递推编程是不可取的,可维护性与可读性都很差。
    mckelvin
        9
    mckelvin  
       2021-05-17 20:49:12 +08:00
    其实你能理解的,就是高中数学里讲的「数学归纳法」。但是理解了数学归纳法不代表每一道这类题目都会做,做得少不会做也很正常。日常写后端最常见的用处就是面试,实际工作中几乎不会遇到。如果不喜欢为了面试而刻意学习动态规划,那就躲开上来就刷算法题的公司吧!
    opengps
        10
    opengps  
       2021-05-17 20:57:04 +08:00   ❤️ 3
    hr 最喜欢问的无聊问题,问你人生规划,答不上来的瞎判定为没目标的摸鱼党
    zhoudaiyu
        11
    zhoudaiyu  
    OP
       2021-05-17 20:57:22 +08:00 via iPhone
    @ysn2233
    @werls
    @secsilm
    @index90 确实是面试受虐了…
    @LeeReamond 照本宣科是背题么
    @Sasasu 有点恐惧动态规划,而且我理解算法本身就很慢,归并排序都看了很久,就是递归没学明白啊
    @powerman 现在都理解不了例题….
    @mckelvin 很少有不问算法的了吧,面个小公司都问个不停
    ClericPy
        12
    ClericPy  
       2021-05-17 21:54:37 +08:00   ❤️ 1
    #10 楼经典...

    我的人生规划就是动态规划, 走一步看一步
    learningman
        13
    learningman  
       2021-05-17 22:02:57 +08:00 via Android
    @ClericPy 那算不上动态规划,动态规划是有严格的公式的。。。
    emSaVya
        14
    emSaVya  
       2021-05-17 22:08:11 +08:00   ❤️ 3
    @ClericPy 人生必然是 greedy 的 要能 dp 那可太爽了
    yogogo
        15
    yogogo  
       2021-05-17 22:11:26 +08:00
    @opengps 实在是想不明白 hr 这么问对公司来说有啥意思
    namelosw
        16
    namelosw  
       2021-05-17 22:15:36 +08:00   ❤️ 3
    > 有点恐惧动态规划,而且我理解算法本身就很慢,归并排序都看了很久,就是递归没学明白啊

    动态规划可以简单约等于递归,你没明白动态规划是因为你没明白递归。

    写动态规划步骤:
    1. 忘记其他的所有东西,状态转移方程之类的,只练写低效递归,保证逻辑正确
    2. 用字典缓存参数对应的函数结果,这个叫 memoization,如果用 Python 就是直接加个 @lru_cache 就行了
    3. 用写好的函数打印前几个结果,找一下规律,然后把内外翻过来,从自顶向下翻译成自底向上就是 DP 了

    专心练第一步就行,熟悉了之后后面两部手到擒来。DP 和 memoization 是方向相反效果类似的,先写 memoization 要比 DP 容易很多。


    > 归并排序都看了很久

    不光是递归没明白,如果你只熟悉递归看明白归并其实还是很困难,算法有很多套路的。

    归并是二叉树后序遍历,因为是后合并,所以就是后序遍历,你把二叉树后序遍历练几遍就会发现代码形状是一样的。
    反过来快排就是二叉树前序遍历,因为是先交换,交换完后面就没事了,所以是前序。

    你感觉很多人看起来理解力爆炸,其实只是他们练得多,而不是聪明。你看一段代码要从 0% 理解到 100%,他看一段代码识别一个模板就等于看完 80%了,再把 20%关键点看一下就懂了。
    namelosw
        17
    namelosw  
       2021-05-17 22:16:52 +08:00
    @ClericPy 你要是不说后半句可能还不会露馅得这么明显……
    ilovekobe1314
        18
    ilovekobe1314  
       2021-05-17 22:17:54 +08:00
    @namelosw 我也是 对面试题非常恐惧 感觉大佬说的很有道理,学习下
    opengps
        19
    opengps  
       2021-05-17 22:20:13 +08:00
    看了半天怎么感觉“动态规划”说的有歧义啊,这到底是技术问题还是职业发展问题?
    ClericPy
        20
    ClericPy  
       2021-05-17 23:10:45 +08:00
    @learningman
    @namelosw

    前半句是之前看到 "人生不可动态规划" 直接反向引用调戏 HR, 后半句确实理解偏了, 太久没关注 DP 了(以前偶尔刷题遇到), 只有点递归和记录子问题最优解的印象, 刚才又搜搜引擎复习了一遍...

    @emSaVya
    如果人生在走下坡路, 前一步总是最优... 现在越活越丧气
    raaaaaar
        21
    raaaaaar  
       2021-05-17 23:13:21 +08:00 via Android
    以前我也挺害怕的,后来学了算法课和数学建模,其实也没有那么恐怖。

    你要说什么计算,操作系统啥的可能对真正开发会有影响,但是这个东西就纯面向面试的东西吧
    raaaaaar
        22
    raaaaaar  
       2021-05-17 23:54:39 +08:00 via Android   ❤️ 2
    贪婪,动态规划,分治,都是把一个复杂的问题划分为子问题来解。

    贪婪是每个子问题都是最优的,但是最终问题一般不是最优解。

    分治的子问题一般是独立的,能够单独求解出来,比如说归并和快排,分成两个子问题排序时,其他子问题是不会影响的。分治的思想就是先分,再治。子问题的类型一般类似,求解方式一样,所以一般用递归,求解完子问题后,再合并求解原问题,比如说二叉树就是一个很常用的分治思想,因为二叉树从定义上来说就是一个递归式的,都能划分为三个节点的子问题,所以很多算法都是差不多的模板。

    而动态规划也是把问题划分为子问题,但是在求解的过程中,子问题有些重复出现了,这个时候我们可以时空权衡,也就是空间换时间,把子问题的解记录下来帮助求解,比如说经典的求斐波那契数列,求 f(6)要算 f(5) 和 f(4),这里要算一边 f(4),而求 f(5)?时又要求 f(4) 和 f(3),显然 f(4) 就重复计算了,那么我们就可以提前把结果存下来,以后用的时候直接查找就行了。转换为迭代就是这个思想。

    那么一般什么问题适合动态规划呢?
    子问题重复:子问题有重复的,这是动态规划优化的原理,当然子问题如果没有重复也可以做,不过就没有意义了。
    无后向性:把问题划分为子问题后,通常子问题是一个线性的链,这个链要是一个马尔可夫链,也就是说,后面阶段(子问题)的解,只和现在这个阶段的解有关,而和以前的解无关。比如求 f(6) 时,结果就只和前一个阶段的 f(5) 和 f(4) 有关,而和其他的无关。
    最优化原理:和贪婪一个思想,也就是说,每个阶段的解必须是最优的,而且通常需要先证明,最终问题的最优解等价于局部各阶段最优,这个时候才会使用动态规划。

    动态规划的实质是什么?
    分治+时空权衡解决冗余

    那么动态规划应该具体怎么做?
    分析问题的结构,看它是不是满足上面的三个原则,或者能转换为类似的问题。比如说,f(6) 能分为 f(4) 和 f(3),这就是一个阶段,并且阶段有重复的,那么这个问题就能用动态规划来做。一般可以画决策树来帮助理解,也就是说,要解决这个问题,需要解决那些问题?这样一层层的分析下去的一棵树。

    递归求解。我们可以从原问题开始一个阶段一个阶段的往下求解,也可以反过来从最低的阶段求解,而在这个过程中,我们通常会发现不同阶段间的转移是有规律的,通常问题的重点就在于如何找到这个状态转移方程。

    根据得到的值,求解最优值。

    在找转移方程的时候,问题怎么分阶段,每个阶段具体和什么信息有关,又怎么用符号来表示一个阶段,最后才是怎么找出阶段间的关系。通常动态规划中有一种常见的划分阶段的方式,那就是选择还是不选择这样二元的关系。

    比如说在组合问题中,要对 n 个数选择 k 个数,我们一个个的选,对于每一个数,就有选或者不选两种可能,如果第一个数选,那么还需要从 n-1 个数里选 k-1 数出来,如果选,那么需要从 n-1 个数里选 k 个数,最终的结果就是这两种情况的和。在这里我们以数的选与不选作为阶段,同时也自然推出了转移方程,最终的结果是和,但是比如背包,或者最短路径中,通常是多个值的最值。
    fantastM
        23
    fantastM  
       2021-05-18 00:53:42 +08:00
    > 有点恐惧动态规划......

    曾经我也是这样,一度怀疑自己的智商,但当我逐字逐句地看完《算法导论》之后,我就不再害怕了
    beidounanxizi
        24
    beidounanxizi  
       2021-05-18 01:21:45 +08:00
    大部分面试官水平也不会超过 codeforce 2K 以上的
    做不出来 大概率是刷题不够 又容易忘记吧
    786375312123
        25
    786375312123  
       2021-05-18 01:27:56 +08:00
    到目前为止 FAANG 面了个遍,一次动态规划都没遇到过
    binux
        26
    binux  
       2021-05-18 02:22:50 +08:00 via Android
    那要不你找找你擅长的?
    Hsinyao
        27
    Hsinyao  
       2021-05-18 02:45:40 +08:00
    当然没有影响,但是面试就是要问啊,不会就没有工作,那能怎么办呢
    Mirage09
        28
    Mirage09  
       2021-05-18 03:07:11 +08:00 via iPhone
    我个人觉得面试面 dp 还要最优解是件很无聊的事情…
    JoStar
        29
    JoStar  
       2021-05-18 09:37:30 +08:00
    @fantastM 这本书真有这么强?适合新手?
    fantastM
        30
    fantastM  
       2021-05-18 09:58:12 +08:00
    @JoStar #29
    > 这本书真有这么强?
    英文版豆瓣 9.5 分,中文版豆瓣 9.2 分

    > 适合新手?
    书中的译者序章节说,这书是斯坦福大学的教材
    woodensail
        31
    woodensail  
       2021-05-18 15:00:39 +08:00
    @powerman 你理解错他的意思了,他的意思是所有计算过的数据都存下来,省得下次重新算。至于计算方式是啥并不重要。
    cornetCat
        32
    cornetCat  
       2021-05-19 15:33:12 +08:00   ❤️ 1
    b 站有个 up 讲这个感觉讲的很好,正月点灯笼( https://space.bilibili.com/24014925/)非常推荐
    zhoudaiyu
        33
    zhoudaiyu  
    OP
       2021-05-19 18:56:21 +08:00
    @cornetCat #32 感觉这个 up 主讲的很不错啊,感谢感谢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4921 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 10:01 · PVG 18:01 · LAX 02:01 · JFK 05:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.