这是一个创建于 1479 天前的主题，其中的信息可能已经有所发展或是发生改变。
递归,回溯在业务场景中时不时能学以致用, 反观 dp 除了算法题自 high 目前完全没实际场景用到.
难道是因为我是个 crud boy 的原因?
在其他领域才是他大放异彩的时刻?
就纯粹做题用,真的挺蠢得
求解
第 1 条附言 · 2020-11-16 13:08:23 +08:00
 |
1
murmur 2020-11-16 09:29:10 +08:00
不只是 dp 有这个问题，一般的场景都能用库解决，想用你的算法替代库算法，首先你得证明在业务上你的算法好于库算法，稳定性、 容错不能比库差，但是没特殊需求，找个 star 多的库就行了。
|
 |
2
hyserendipity 2020-11-16 09:37:57 +08:00
更多是因为实际场景能用就行，这显然不是 dp 价值的问题。
|
 |
3
loliordie 2020-11-16 09:38:57 +08:00 via Android
有用 但是超过 99%的程序员用不上
恕我直言 如果在美国面试问 dp 要么你面的是 Google 要么纯粹就是不想让你进 |
 |
4
huai 2020-11-16 09:57:51 +08:00
DP 自下而上，没记错的话，比递归好一些。递归的层级太多，好像会引发问题（没碰到，确实实际中能用就行
|
 |
5
dtgxx 2020-11-16 09:59:36 +08:00
数据结构算法都是写框架或者底层实现的人用的，为了性能。 只是培养你这方面的思维，也应对面试。 代码都写不完哪有时间想什么最佳算法。
|
 |
6
tamer OP @murmur 并不是说要写加密算法 /快排之类的顶替已有库,
我理解的是在刷题获得的解题思路会给业务场景提供帮助, 涉及到数据处理清洗, 以及一些奇形怪状的需求, 在保证效率的同时满足要求 回头看的话,目前个人而言最没用的题目就是各种 dp 以及奇淫技巧的解题方法, 有高考题还有中式英语题那味道了 先有解法后有题 |
 |
7
Escapist367 2020-11-16 10:09:56 +08:00
看你的领域了。
我自己的话因为会去做序列生成，在 viterbi 或者是 beam search 的时候，必然会需要写 dp~ |
 |
8
lights 2020-11-16 10:13:21 +08:00 via iPhone
游戏开发类偶尔会用到简单的 DP，经典的比如自动吃经验包吃最少数量的经验包
|
 |
9
nevin47 2020-11-16 10:16:18 +08:00
递归的复杂度太高，做大规模路由的时候，DP 就是比递归快
业务场景中用得其实不少，但是 CURD 的场景肯定没必要用，背后的组件都帮你写好了 |
 |
10
zy445566 2020-11-16 10:24:29 +08:00
开启新的思维方法，就比如找硬币问题，如果用压栈的方法也可以解决，但是如果使用 dp，把每个硬币拆解成单一问题，反而代码还简单很多，维护性就高了
|
 |
11
remarrexxar 2020-11-16 10:27:22 +08:00
@huai #4 递归太深就会爆栈了
|
|
12
murmur 2020-11-16 10:27:45 +08:00
@lights 见过另一种实现思路，按照一定的顺序吃经验，如果溢出就退一部分给你
比如强化材料有 100 1000 10000 的三种，需要 66000 点经验，那我就可以直接吃 70000，然后返还 4000 |
 |
13
55savage 2020-11-16 10:56:21 +08:00
我上周刚上完一节图形学的课，讲了 seam carving，里面用到了 DP
|
 |
14
jmc891205 2020-11-16 11:04:54 +08:00
没错啊。。。因为你是个因为你平常都在做 CRUD
|
 |
15
maplelin 2020-11-16 11:18:10 +08:00
DP 说白了不就是以空间换时间的回溯 /递归算法吗
|
 |
16
Jooooooooo 2020-11-16 11:18:33 +08:00
把部分结果记录下来 这种思想很多地方都能用上啊, 甚至不限于编程领域.
|
|
17
tamer OP @lights 看来还是领域问题,hh
dp 个人感觉最难的一步就是建模, 将实际问题转换成状态方程, 难度巨高不说, 而且处理能力太局限了, dp[n] n 如果特别大就得另辟蹊径了 没想到真的有业务场景可以用到, 长见识了, 3Q |
|
18
tamer OP @Jooooooooo 平时回溯的剪枝也基本会有吧, dp 最精华的是动态方程这块,个人理解,也是难点所在,最消磨时间的部分
|
 |
20
newtype0092 2020-11-16 11:45:04 +08:00
@tamer 游戏里因为有各种场景所以会用到很多平时不常用的算法，DP 的话之前自己写过：
整理背包，暗黑那种，每个物品占的格子的数量和形状不同，怎么排列浪费空间最少。 麻将，之前哥们写的 N 重循环太卡了，优化了一下可以瞬间检定所有可能的和牌。 |
 |
21
b1ackjack 2020-11-16 11:49:31 +08:00
之前写过一个分词器，没使用 dp 的话对于连词长句子会非常耗时，但是用了 dp 很快就能出结果，dp 重要的是思想
|
 |
22
favourstreet 2020-11-16 12:24:18 +08:00 via Android
优化问题的解法永远不会没用啊，因为就算完全不像的问题也经常能通过一些操作变换成最优化的求解问题，dp 作为其中一大类怎能没用
|
 |
23
DarkCat123 2020-11-16 12:27:19 +08:00
|
 |
24
happinessnch 2020-11-16 13:04:09 +08:00
其实就是纯做题，就算 DP 可以找到一些业务场景应用，
那图论、几何、数论在该场景下能用的到吗？ 如果想要通吃各种比赛、面试，每个基础算法都要涉及练习， 但是要想找到各个算法都能应用场景，那完全不可能，所以，这种情况下刷题就不是追求学以致用， 做题就是为了做题而已，目的不是比赛，就是面试。 |
 |
25
dayeye2006199 2020-11-17 07:00:57 +08:00
@happinessnch 算法被设计出来肯定是为了解决特定问题的。简单举几个最常见的例子
图论：pip，conda 或者 npm 这类依赖管理包工具里面，就使用了图论里面的依赖路径算法 几何：各种图形应用，arvr，游戏开发，图形学基本都是几何和代数 数论：常见的不对称加密，RSA 算法，都是数论的应用 |
|
26
happinessnch 2020-11-17 08:26:52 +08:00
|
Select Language