感觉careercup的作者对DP的理解有问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

感觉careercup的作者对DP的理解有问题

感觉careercup的作者对DP的理解有问题# JobHunting - 待字闺中

J*a2013-05-05 07:05

1 楼

看过第五版的人说说是不是这样
她的所谓DP都是把中间结果存在一个hashTable里
下次算之前看看那里面有没有
但真的DP有两个要点
1）保存子问题的结果
2）子问题有序
但是作者几乎从没注意第二个问题所有的还按递归算法那么算，就多加个hash
所以很多题依然是指数复杂度的（部分题真DP是可以降到n^2或n^3）
大家觉得呢

d*t2013-05-05 07:05

2 楼

子问题自然就有序了的吧。再说有序无序对复杂度也没影响。

【在 J*****a 的大作中提到】

: 看过第五版的人说说是不是这样
: 她的所谓DP都是把中间结果存在一个hashTable里
: 下次算之前看看那里面有没有
: 但真的DP有两个要点
: 1）保存子问题的结果
: 2）子问题有序
: 但是作者几乎从没注意第二个问题所有的还按递归算法那么算，就多加个hash
: 所以很多题依然是指数复杂度的（部分题真DP是可以降到n^2或n^3）
: 大家觉得呢

J*a2013-05-05 07:05

3 楼

不是啊她还是按递归那个顺序算
比如背包问题 dp的矩阵应该一行一行的算矩阵每个元素只要遍历一次
比如断字问题就应该先算对角线向左上方向遍历
而且DP都是先算小子问题在算大子问题顺序都是精心安排才能最大限度降复杂度
但是她还是按照递归算法访问那些子问题所以先碰到的是大问题因此就肯定有很多
mismatch （在hashtable里找不到）所以复杂度肯定高了啊

【在 d********t 的大作中提到】

: 子问题自然就有序了的吧。再说有序无序对复杂度也没影响。

s*12013-05-05 07:05

4 楼

那个本来也是DP，用MEMO实现的DP，实现方式不同而已，而且这种写起来简单，在有些
情况下还能避免求解无用的子问题。lz可能只是以前没见过这个吧，没问题的。但是那
本书本身质量不高是真的。

b*72013-05-05 07:05

5 楼

同意shaoshuai321。
memoization方式处理DP问题，这样可以让DP按top-down的方式递归实现。
在有些bottom-up方式难处理的场合，用这种技术可以很方便的写出code。
比如个人认为这个题用memoization难度会降低很多，也容易bug free
http://www.geeksforgeeks.org/largest-independent-set-problem/

t*d2013-05-05 07:05

6 楼

只要子问题没有循环依赖就应该没问题

★ 发自iPhone App: ChineseWeb 7.8

【在 J*****a 的大作中提到】

p*22013-05-05 07:05

7 楼

作者对DP的理解局限了。不过她的理解对于初学DP也算是挺有用的。面试这么干也可以
。更容易bug free。

J*a2013-05-05 07:05

8 楼

er。。。。
我还是持保留意见
比如17.14的答案就有问题，而且她的所谓dp算法复杂度明显比传统Bottom up的DP高（
有指数次递归调用）

J*a2013-05-05 07:05

9 楼

我承认这样写起来简单
但是这样做，有些本可降到n^2或者n^3的题，用这种方法还是需要指数复杂度，因为有
指数次函数调用

【在 s**********1 的大作中提到】

: 那个本来也是DP，用MEMO实现的DP，实现方式不同而已，而且这种写起来简单，在有些
: 情况下还能避免求解无用的子问题。lz可能只是以前没见过这个吧，没问题的。但是那
: 本书本身质量不高是真的。

b*n2013-05-05 07:05

10 楼

memoization啊，clrs里面也有，时间复杂度上没有问题的，
最大问题是space complexity，及有可能stack overflow

【在 J*****a 的大作中提到】

s*12013-05-05 07:05

11 楼

你理解错了，不会有指数复杂度，因为每个子问题只算一次，后面就有答案了

【在 J*****a 的大作中提到】

: 我承认这样写起来简单
: 但是这样做，有些本可降到n^2或者n^3的题，用这种方法还是需要指数复杂度，因为有
: 指数次函数调用

J*a2013-05-05 07:05

12 楼

我知道每个子问题只算一次
但是递归调用还是可能有指数次比如第17章最后一题的答案
因为它没有按子问题从小到大的顺序计算，所有查hash表有很多次是查不到的，查不到
就要调用
就算每次递归调用是O（1）所以解法还可能是指数复杂度

【在 s**********1 的大作中提到】

: 你理解错了，不会有指数复杂度，因为每个子问题只算一次，后面就有答案了

J*a2013-05-05 07:05

13 楼

ok 不是指数次比Dp稍高但不是指数

t*a2013-05-05 07:05

14 楼

memoize是相当聪明而且省事的办法。它只算需要算的，复杂度不会比递推高。
建议楼主耐心下来把两种方法都做做看以后再下结论。

t*a2013-05-05 07:05

15 楼

space complexity是个问题，有些问题不需要保存所有中间计算结果的。如果语言级别
提供比较聪明的memoize方式，可以有选择的遗忘，就好办了。
stack overflow的事情很讨厌。by default, stack内存就只有1M，相对现在的机器容
量而言太少了。JVM可以自己调节stack分配大小，从而可以递归很多次。

【在 b******n 的大作中提到】

: memoization啊，clrs里面也有，时间复杂度上没有问题的，
: 最大问题是space complexity，及有可能stack overflow

p*22013-05-05 07:05

16 楼

支持大牛。很多时候dfs反而更快

【在 t****a 的大作中提到】

: memoize是相当聪明而且省事的办法。它只算需要算的，复杂度不会比递推高。
: 建议楼主耐心下来把两种方法都做做看以后再下结论。

f*r2013-05-05 07:05

17 楼

计算的overhead在于hash function和hashmap access，这两个忽略的话topdown方法的
复杂度<=bottom up方法的复杂度吧。

★ 发自iPhone App: ChineseWeb 7.8

【在 J*****a 的大作中提到】

: ok 不是指数次比Dp稍高但不是指数