对 dp 的实际价值的怀疑?

[tamer]

递归,回溯在业务场景中时不时能学以致用, 反观 dp 除了算法题自 high 目前完全没实际场景用到.

难道是因为我是个 crud boy 的原因?

在其他领域才是他大放异彩的时刻?

就纯粹做题用,真的挺蠢得

求解

[murmur]

不只是 dp 有这个问题，一般的场景都能用库解决，想用你的算法替代库算法，首先你得证明在业务上你的算法好于库算法，稳定性、 容错不能比库差，但是没特殊需求，找个 star 多的库就行了。

[hyserendipity]

更多是因为实际场景能用就行，这显然不是 dp 价值的问题。

[loliordie]

有用 但是超过 99%的程序员用不上

恕我直言 如果在美国面试问 dp 要么你面的是 Google 要么纯粹就是不想让你进

[huai]

DP 自下而上，没记错的话，比递归好一些。递归的层级太多，好像会引发问题（没碰到，确实实际中能用就行

[dtgxx]

数据结构算法都是写框架或者底层实现的人用的，为了性能。 只是培养你这方面的思维，也应对面试。 代码都写不完哪有时间想什么最佳算法。

[tamer]

@murmur 并不是说要写加密算法 /快排之类的顶替已有库,
我理解的是在刷题获得的解题思路会给业务场景提供帮助, 涉及到数据处理清洗, 以及一些奇形怪状的需求, 在保证效率的同时满足要求

回头看的话,目前个人而言最没用的题目就是各种 dp 以及奇淫技巧的解题方法, 有高考题还有中式英语题那味道了
先有解法后有题

[Escapist367]

看你的领域了。
我自己的话因为会去做序列生成，在 viterbi 或者是 beam search 的时候，必然会需要写 dp~

[lights]

游戏开发类偶尔会用到简单的 DP，经典的比如自动吃经验包吃最少数量的经验包

[nevin47]

递归的复杂度太高，做大规模路由的时候，DP 就是比递归快

业务场景中用得其实不少，但是 CURD 的场景肯定没必要用，背后的组件都帮你写好了

[zy445566]

开启新的思维方法，就比如找硬币问题，如果用压栈的方法也可以解决，但是如果使用 dp，把每个硬币拆解成单一问题，反而代码还简单很多，维护性就高了

[remarrexxar]

@huai #4 递归太深就会爆栈了

[murmur]

@lights 见过另一种实现思路，按照一定的顺序吃经验，如果溢出就退一部分给你

比如强化材料有 100 1000 10000 的三种，需要 66000 点经验，那我就可以直接吃 70000，然后返还 4000

[55savage]

我上周刚上完一节图形学的课，讲了 seam carving，里面用到了 DP

[jmc891205]

没错啊。。。因为你是个因为你平常都在做 CRUD

[maplelin]

DP 说白了不就是以空间换时间的回溯 /递归算法吗

[Jooooooooo]

把部分结果记录下来 这种思想很多地方都能用上啊, 甚至不限于编程领域.

[tamer]

@lights 看来还是领域问题,hh

dp 个人感觉最难的一步就是建模, 将实际问题转换成状态方程, 难度巨高不说, 而且处理能力太局限了, dp[n] n 如果特别大就得另辟蹊径了

没想到真的有业务场景可以用到, 长见识了, 3Q

[tamer]

@Jooooooooo 平时回溯的剪枝也基本会有吧, dp 最精华的是动态方程这块,个人理解,也是难点所在,最消磨时间的部分

[lights]

@tamer 复杂一些的建模，我也不会，哪怕是刷题的时候复杂一些的 DP 题也是只能抄答案

[newtype0092]

@tamer 游戏里因为有各种场景所以会用到很多平时不常用的算法，DP 的话之前自己写过：
整理背包，暗黑那种，每个物品占的格子的数量和形状不同，怎么排列浪费空间最少。
麻将，之前哥们写的 N 重循环太卡了，优化了一下可以瞬间检定所有可能的和牌。