一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1513|回复: 9
收起左侧

[动态规划] 其实动态规划是不是就是DFS的升级版啊?

[复制链接] |试试Instant~ |关注本帖
kelvinzhong 发表于 2014-1-7 21:38:56 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
RT, 楼主发现用DFS做某些题目会超时,而用DP做就不会,感觉是因为DP把中间运行的值存起来了方便以后用,是不是这么一回事啊?。。。楼主初来乍到...问题弱智求别喷...
linlinying 发表于 2014-1-7 21:43:02 | 显示全部楼层
动态规划其中的一部分又叫记忆化搜索(或者这俩都是一个东西?有点忘了)
通常的dfs做了很多重复的搜索,即在参数一样的情况下因为递归所以重复搜了很多次造成时间更长
经常情况下dfs是指数级而DP可以降到平方甚至线性

DP不完全算是DFS的升级版,因为DFS只是搜索中的一类=。=
要说的话应该是所有搜索的升级版吧~
回复 支持 反对

使用道具 举报

marine 发表于 2014-1-7 22:14:18 | 显示全部楼层
楼主所言极是。

今天看CC150,在Graph那一章看到:DP算法由于会记忆中间结果,因此其效率很高
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-1-8 12:18:25 | 显示全部楼层
递归是自顶向下,DP是自底向上。
回复 支持 反对

使用道具 举报

yang5313876 发表于 2014-1-8 20:37:15 | 显示全部楼层
这两个不能这么比吧。。。
DP is a mathematical optimization and programming method. For many complex problems, there are many subproblems sharing the similar structure. Take advantage of this property. Optimize the algorithm by using the things you have computed and stored. Usually, algorithm with exponential running time could be reduced to polynomial running time.

DFS is just a algorithm to traverse a tree or a graph, nothing special......
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-8 21:04:31 | 显示全部楼层
DP是思想, dfs是实现
就像
Mapreduce是思想,hadoop是实现
回复 支持 反对

使用道具 举报

lenux 发表于 2014-1-9 10:45:04 | 显示全部楼层
DP 是一种内隐式的列举法(implicit enumeration),把一个大问题分散成很多子问题,让你不必把所有的可能组合都列出来就可以找到最佳解,想要知道DP的核心思想可以看一下驿马车问题(Stage coach problem),我会说DP不是一种算法,是一种逻辑推导的方式

然后DP的问题由前往后做和由后往前做都会得到一样的答案,不影响,它困难的地方是在于不同的题目有不同的切入方式,但大体而言都是把State、Stage、Recursive Function这几个关键的东西找出来就很好求解了
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-1-9 12:08:30 | 显示全部楼层
DP能解决的问题,DFS都能解决,感觉DP是把DFS中的一类有特殊性质的问题提炼出来了吧
回复 支持 反对

使用道具 举报

lvchaoshuai 发表于 2014-1-9 13:02:26 | 显示全部楼层
记忆化搜索就可以看作是DP,避免了重复计算。
回复 支持 反对

使用道具 举报

lzsilica 发表于 2014-1-15 16:05:02 | 显示全部楼层
本帖最后由 lzsilica 于 2014-1-15 16:06 编辑

个人理解,DP一方面是化整为零、化大为小(这一点是说有的问题直接做甚至都没有思路,从DP看却可能有突破口), 另一个就是避免重复计算(可能有了一种算法能解决问题,但是DP能让算法更有效率)。

DP可以是递归的形式(使用memorization, 比如wordladder II), 也可以不是递归的形式(比如longest palindrome substring, path sum)。 而DFS通常是递归的形式,当然也可以不是,但是当DFS是非递归的时候,也很难和DP进行比较。

说 DP 是升级版的DFS 并不稳妥。我更倾向于Readman说的DP是一种思想。 使用DP必须对问题有一个清晰的认识,对不同级别规模问题(n vs n-1 / n-2 / ...)之间的联系和转换有把握(以公式的形式严格表达出来)。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 08:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表