普通后端程序员,非算法岗
1
ysn2233 2021-05-17 19:07:35 +08:00
没影响
|
2
werls 2021-05-17 19:07:41 +08:00 1
平时就 crud 。有什么影响?
|
3
secsilm 2021-05-17 19:11:02 +08:00 via Android
这和是否算法岗( AI )无关吧,
|
4
index90 2021-05-17 19:13:12 +08:00
被面试虐了?用来在众多合适的候选人中,继续筛选用的。
|
5
LeeReamond 2021-05-17 19:29:45 +08:00 via Android
如果你指不能设计 dp 算法的话,没什么影响,应该大多数人不具备这个能力。如果你指不能理解个别算法的话,应该没什么影响。如果你无法照本宣科实现?那似乎发展会非常受限?
|
6
WhereverYouGo 2021-05-17 19:52:20 +08:00
有概率无法通过字节、阿里、腾讯 or 其他公司的某一轮面试😼
|
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 这和你无脑加缓存有啥区别 |
8
powerman 2021-05-17 20:31:38 +08:00 1
@Sasasu 这只是动态规划的另外一种实现方式,实际上递归调用是与迭代递推是等价的,而且前者比后者更容易理解与实现,
DP 的难点不是编程,难点是推导出递推方程式,而且推导递推公式非常难,而且不是那么显然,而用递归缓存子问题的结果是比较容易理解的方式,实现起来比较容易,维护比较简单,从工程的角度来讲,迭代的递推编程是不可取的,可维护性与可读性都很差。 |
9
mckelvin 2021-05-17 20:49:12 +08:00
其实你能理解的,就是高中数学里讲的「数学归纳法」。但是理解了数学归纳法不代表每一道这类题目都会做,做得少不会做也很正常。日常写后端最常见的用处就是面试,实际工作中几乎不会遇到。如果不喜欢为了面试而刻意学习动态规划,那就躲开上来就刷算法题的公司吧!
|
10
opengps 2021-05-17 20:57:04 +08:00 3
hr 最喜欢问的无聊问题,问你人生规划,答不上来的瞎判定为没目标的摸鱼党
|
11
zhoudaiyu OP |
12
ClericPy 2021-05-17 21:54:37 +08:00 1
#10 楼经典...
我的人生规划就是动态规划, 走一步看一步 |
13
learningman 2021-05-17 22:02:57 +08:00 via Android
@ClericPy 那算不上动态规划,动态规划是有严格的公式的。。。
|
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%关键点看一下就懂了。 |
18
ilovekobe1314 2021-05-17 22:17:54 +08:00
@namelosw 我也是 对面试题非常恐惧 感觉大佬说的很有道理,学习下
|
19
opengps 2021-05-17 22:20:13 +08:00
看了半天怎么感觉“动态规划”说的有歧义啊,这到底是技术问题还是职业发展问题?
|
20
ClericPy 2021-05-17 23:10:45 +08:00
@learningman
@namelosw 前半句是之前看到 "人生不可动态规划" 直接反向引用调戏 HR, 后半句确实理解偏了, 太久没关注 DP 了(以前偶尔刷题遇到), 只有点递归和记录子问题最优解的印象, 刚才又搜搜引擎复习了一遍... @emSaVya 如果人生在走下坡路, 前一步总是最优... 现在越活越丧气 |
21
raaaaaar 2021-05-17 23:13:21 +08:00 via Android
以前我也挺害怕的,后来学了算法课和数学建模,其实也没有那么恐怖。
你要说什么计算,操作系统啥的可能对真正开发会有影响,但是这个东西就纯面向面试的东西吧 |
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 个数,最终的结果就是这两种情况的和。在这里我们以数的选与不选作为阶段,同时也自然推出了转移方程,最终的结果是和,但是比如背包,或者最短路径中,通常是多个值的最值。 |
23
fantastM 2021-05-18 00:53:42 +08:00
> 有点恐惧动态规划......
曾经我也是这样,一度怀疑自己的智商,但当我逐字逐句地看完《算法导论》之后,我就不再害怕了 |
24
beidounanxizi 2021-05-18 01:21:45 +08:00
大部分面试官水平也不会超过 codeforce 2K 以上的
做不出来 大概率是刷题不够 又容易忘记吧 |
25
786375312123 2021-05-18 01:27:56 +08:00
到目前为止 FAANG 面了个遍,一次动态规划都没遇到过
|
26
binux 2021-05-18 02:22:50 +08:00 via Android
那要不你找找你擅长的?
|
27
Hsinyao 2021-05-18 02:45:40 +08:00
当然没有影响,但是面试就是要问啊,不会就没有工作,那能怎么办呢
|
28
Mirage09 2021-05-18 03:07:11 +08:00 via iPhone
我个人觉得面试面 dp 还要最优解是件很无聊的事情…
|
30
fantastM 2021-05-18 09:58:12 +08:00
|
31
woodensail 2021-05-18 15:00:39 +08:00
@powerman 你理解错他的意思了,他的意思是所有计算过的数据都存下来,省得下次重新算。至于计算方式是啥并不重要。
|
32
cornetCat 2021-05-19 15:33:12 +08:00 1
b 站有个 up 讲这个感觉讲的很好,正月点灯笼( https://space.bilibili.com/24014925/)非常推荐
|