Redian新闻
>
刷题问题:DP和DFS+memorization哪个快?
avatar
刷题问题:DP和DFS+memorization哪个快?# JobHunting - 待字闺中
o*m
1
朋友的公司要来三藩参加一年一度的游戏开发者大会:
Game Developer Conference 2011,
Moscone Center, San Francisco, CA
2/28/11 - 3/4/11
Exhibit: 3/2/11 - 3/4/11
现有多余的参展票贱价出售, 票的细节及展会信息如下:
http://www.gdconf.com/attend/passes.html#descriptions
出售的票如下:
All access, 共3张, $1100/ticket, 提前注册票是$1475, 这个便宜了25%。.
Expo, 共10张, $150/ticket, 提前注册票是$195, 这个便宜了23%。
除了Expo 需要现场注册, All access是需要先填写信息。 All access票已经填上了
我朋友公司的信息,入场是不用核对身份证或者护照号码的。在您入场时, 我们可以
把票给你。
请有兴趣者,please pm me。 谢谢!
ps, 去年我参加了这个大会, 你可以现场体验众多游戏厂商的新产品, 你可以遇见许
多优秀的游戏制作者。 最好玩的事有一个独立游戏开发者的颁奖晚会, 他们评出从手
机游戏, 到掌上机, 以及多人联网游戏的本年度最佳游戏。 在展会上也可以试玩。
一定可以会让你大饱眼福。
avatar
e*y
2
譬如regular expression matching
可以直接用DP代表 s[0...i-1] 和 p[0...j-1] 是否match,从下往上做
或者可以用recursion+memorization做
这两种方法哪个更快?求大牛指导细节。
avatar
T*n
3
可以带来多少利润?
avatar
b*d
4
当然是dp, guaranteed O(n*m) time, O(n) space
memorization search worst case还是exponential的复杂度,O(m*n) space, 只是找
不到dp算法时没办法才用。
avatar
x*z
5
某些问题,加上memorization之后,不管什么搜索路径,实际工作量是一样的。如果只
要求找到一个结果或者判断是否存在,dfs搜到目标就直接返回了,比dp快是常有的事
avatar
h*e
6
dfs 用到栈空间有可能爆栈,另外压栈退栈是个开销, dp有可能搜到多余的状态。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。