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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1067 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

后端

程序员

算法

动态

33 条回复 • 2021-05-19 18:56:21 +08:00

ysn2233

2021-05-17 19:07:35 +08:00

没影响

werls

2021-05-17 19:07:41 +08:00

平时就 crud 。有什么影响？

secsilm

2021-05-17 19:11:02 +08:00 via Android

这和是否算法岗（ AI ）无关吧，

index90

2021-05-17 19:13:12 +08:00

被面试虐了？用来在众多合适的候选人中，继续筛选用的。

LeeReamond

2021-05-17 19:29:45 +08:00 via Android

如果你指不能设计 dp 算法的话，没什么影响，应该大多数人不具备这个能力。如果你指不能理解个别算法的话，应该没什么影响。如果你无法照本宣科实现？那似乎发展会非常受限？

WhereverYouGo

2021-05-17 19:52:20 +08:00

有概率无法通过字节、阿里、腾讯 or 其他公司的某一轮面试😼

Sasasu

2021-05-17 20:24:13 +08:00

你先撇开状态转移方程那一堆。

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

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

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

这和你无脑加缓存有啥区别

powerman

2021-05-17 20:31:38 +08:00

@Sasasu 这只是动态规划的另外一种实现方式，实际上递归调用是与迭代递推是等价的，而且前者比后者更容易理解与实现，

DP 的难点不是编程，难点是推导出递推方程式，而且推导递推公式非常难，而且不是那么显然，而用递归缓存子问题的结果是比较容易理解的方式，实现起来比较容易，维护比较简单，从工程的角度来讲，迭代的递推编程是不可取的，可维护性与可读性都很差。

mckelvin

2021-05-17 20:49:12 +08:00

其实你能理解的，就是高中数学里讲的「数学归纳法」。但是理解了数学归纳法不代表每一道这类题目都会做，做得少不会做也很正常。日常写后端最常见的用处就是面试，实际工作中几乎不会遇到。如果不喜欢为了面试而刻意学习动态规划，那就躲开上来就刷算法题的公司吧！

opengps

2021-05-17 20:57:04 +08:00

hr 最喜欢问的无聊问题，问你人生规划，答不上来的瞎判定为没目标的摸鱼党

zhoudaiyu

2021-05-17 20:57:22 +08:00 via iPhone

@ysn2233
@werls
@secsilm
@index90 确实是面试受虐了…
@LeeReamond 照本宣科是背题么
@Sasasu 有点恐惧动态规划，而且我理解算法本身就很慢，归并排序都看了很久，就是递归没学明白啊
@powerman 现在都理解不了例题….
@mckelvin 很少有不问算法的了吧，面个小公司都问个不停

ClericPy

2021-05-17 21:54:37 +08:00

#10 楼经典...

我的人生规划就是动态规划, 走一步看一步

learningman

2021-05-17 22:02:57 +08:00 via Android

@ClericPy 那算不上动态规划，动态规划是有严格的公式的。。。

emSaVya

2021-05-17 22:08:11 +08:00

@ClericPy 人生必然是 greedy 的要能 dp 那可太爽了

yogogo

2021-05-17 22:11:26 +08:00

@opengps 实在是想不明白 hr 这么问对公司来说有啥意思

namelosw

2021-05-17 22:15:36 +08:00

> 有点恐惧动态规划，而且我理解算法本身就很慢，归并排序都看了很久，就是递归没学明白啊

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

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

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

> 归并排序都看了很久

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

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

你感觉很多人看起来理解力爆炸，其实只是他们练得多，而不是聪明。你看一段代码要从 0% 理解到 100%，他看一段代码识别一个模板就等于看完 80%了，再把 20%关键点看一下就懂了。

namelosw

2021-05-17 22:16:52 +08:00

@ClericPy 你要是不说后半句可能还不会露馅得这么明显……

ilovekobe1314

2021-05-17 22:17:54 +08:00

@namelosw 我也是对面试题非常恐惧感觉大佬说的很有道理，学习下

opengps

2021-05-17 22:20:13 +08:00

看了半天怎么感觉“动态规划”说的有歧义啊，这到底是技术问题还是职业发展问题？

ClericPy

2021-05-17 23:10:45 +08:00

@learningman
@namelosw

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

@emSaVya
如果人生在走下坡路, 前一步总是最优... 现在越活越丧气

raaaaaar

2021-05-17 23:13:21 +08:00 via Android

以前我也挺害怕的，后来学了算法课和数学建模，其实也没有那么恐怖。

你要说什么计算，操作系统啥的可能对真正开发会有影响，但是这个东西就纯面向面试的东西吧

raaaaaar

2021-05-17 23:54:39 +08:00 via Android

贪婪，动态规划，分治，都是把一个复杂的问题划分为子问题来解。

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

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

而动态规划也是把问题划分为子问题，但是在求解的过程中，子问题有些重复出现了，这个时候我们可以时空权衡，也就是空间换时间，把子问题的解记录下来帮助求解，比如说经典的求斐波那契数列，求 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 个数，最终的结果就是这两种情况的和。在这里我们以数的选与不选作为阶段，同时也自然推出了转移方程，最终的结果是和，但是比如背包，或者最短路径中，通常是多个值的最值。