e**y
发帖数: 784 | 1 譬如regular expression matching
可以直接用DP代表 s[0...i-1] 和 p[0...j-1] 是否match，从下往上做
或者可以用recursion+memorization做
这两种方法哪个更快？求大牛指导细节。 | b******d
发帖数: 794 | 2 当然是dp, guaranteed O(n*m) time, O(n) space
memorization search worst case还是exponential的复杂度，O(m*n) space, 只是找
不到dp算法时没办法才用。 | x*****z
发帖数: 15 | 3 某些问题，加上memorization之后，不管什么搜索路径，实际工作量是一样的。如果只
要求找到一个结果或者判断是否存在，dfs搜到目标就直接返回了，比dp快是常有的事
。 | h*******e
发帖数: 1377 | 4 dfs 用到栈空间有可能爆栈，另外压栈退栈是个开销， dp有可能搜到多余的状态。 |
|
