J*****a
发帖数: 4262 | 1 看过第五版的人说说 是不是这样
她的所谓DP都是把中间结果存在一个hashTable里
下次算之前看看那里面有没有
但真的DP有两个要点
1）保存子问题的结果
2）子问题有序
但是作者几乎从没注意第二个问题 所有的还按递归算法那么算，就多加个hash
所以很多题依然是指数复杂度的 （部分题真DP是可以降到n^2或n^3）
大家觉得呢 |
d********t
发帖数: 9628 | 2 子问题自然就有序了的吧。再说有序无序对复杂度也没影响。
【在 J*****a 的大作中提到】
: 看过第五版的人说说 是不是这样
: 她的所谓DP都是把中间结果存在一个hashTable里
: 下次算之前看看那里面有没有
: 但真的DP有两个要点
: 1）保存子问题的结果
: 2）子问题有序
: 但是作者几乎从没注意第二个问题 所有的还按递归算法那么算，就多加个hash
: 所以很多题依然是指数复杂度的 （部分题真DP是可以降到n^2或n^3）
: 大家觉得呢
|
J*****a
发帖数: 4262 | 3 不是啊 她还是按递归那个顺序算
比如背包问题 dp的矩阵应该一行一行的算 矩阵每个元素只要遍历一次
比如断字问题 就应该先算对角线 向左上方向遍历
而且DP都是先算小子问题 在算大子问题 顺序都是精心安排才能最大限度降复杂度
但是她还是按照递归算法访问那些子问题 所以先碰到的是大问题 因此就肯定有很多
mismatch （在hashtable里找不到） 所以复杂度肯定高了啊
【在 d********t 的大作中提到】
: 子问题自然就有序了的吧。再说有序无序对复杂度也没影响。
|
s**********1
发帖数: 58 | 4 那个本来也是DP，用MEMO实现的DP，实现方式不同而已，而且这种写起来简单，在有些
情况下还能避免求解无用的子问题。lz可能只是以前没见过这个吧，没问题的。但是那
本书本身质量不高是真的。 |
b******7
发帖数: 92 | 5 同意shaoshuai321。
memoization方式处理DP问题，这样可以让DP按top-down的方式递归实现。
在有些bottom-up方式难处理的场合，用这种技术可以很方便的写出code。
比如个人认为这个题用memoization难度会降低很多，也容易bug free
http://www.geeksforgeeks.org/largest-independent-set-problem/ |
t****d
发帖数: 423 | 6 只要子问题没有循环依赖就应该没问题
★ 发自iPhone App: ChineseWeb 7.8
【在 J*****a 的大作中提到】
: 看过第五版的人说说 是不是这样
: 她的所谓DP都是把中间结果存在一个hashTable里
: 下次算之前看看那里面有没有
: 但真的DP有两个要点
: 1）保存子问题的结果
: 2）子问题有序
: 但是作者几乎从没注意第二个问题 所有的还按递归算法那么算，就多加个hash
: 所以很多题依然是指数复杂度的 （部分题真DP是可以降到n^2或n^3）
: 大家觉得呢
|
p*****2
发帖数: 21240 | 7 作者对DP的理解局限了。不过她的理解对于初学DP也算是挺有用的。面试这么干也可以
。更容易bug free。 |
J*****a
发帖数: 4262 | 8 er。。。。
我还是持保留意见
比如17.14的答案就有问题，而且她的所谓dp算法复杂度明显比传统Bottom up的DP高（
有指数次递归调用） |
J*****a
发帖数: 4262 | 9 我承认这样写起来简单
但是这样做，有些本可降到n^2或者n^3的题，用这种方法还是需要指数复杂度，因为有
指数次函数调用
【在 s**********1 的大作中提到】
: 那个本来也是DP，用MEMO实现的DP，实现方式不同而已，而且这种写起来简单，在有些
: 情况下还能避免求解无用的子问题。lz可能只是以前没见过这个吧，没问题的。但是那
: 本书本身质量不高是真的。
|
b******n
发帖数: 823 | 10 memoization啊，clrs里面也有，时间复杂度上没有问题的，
最大问题是space complexity，及有可能stack overflow
【在 J*****a 的大作中提到】
: 看过第五版的人说说 是不是这样
: 她的所谓DP都是把中间结果存在一个hashTable里
: 下次算之前看看那里面有没有
: 但真的DP有两个要点
: 1）保存子问题的结果
: 2）子问题有序
: 但是作者几乎从没注意第二个问题 所有的还按递归算法那么算，就多加个hash
: 所以很多题依然是指数复杂度的 （部分题真DP是可以降到n^2或n^3）
: 大家觉得呢
|
|
|
s**********1
发帖数: 58 | 11 你理解错了，不会有指数复杂度，因为每个子问题只算一次，后面就有答案了
【在 J*****a 的大作中提到】
: 我承认这样写起来简单
: 但是这样做，有些本可降到n^2或者n^3的题，用这种方法还是需要指数复杂度，因为有
: 指数次函数调用
|
J*****a
发帖数: 4262 | 12 我知道每个子问题只算一次
但是递归调用还是可能有指数次 比如第17章最后一题的答案
因为它没有按子问题从小到大的顺序计算，所有查hash表有很多次是查不到的，查不到
就要调用
就算每次递归调用是O（1） 所以解法还可能是指数复杂度
【在 s**********1 的大作中提到】
: 你理解错了，不会有指数复杂度，因为每个子问题只算一次，后面就有答案了
|
J*****a
发帖数: 4262 | |
t****a
发帖数: 1212 | 14 memoize是相当聪明而且省事的办法。它只算需要算的，复杂度不会比递推高。
建议楼主耐心下来把两种方法都做做看以后再下结论。 |
t****a
发帖数: 1212 | 15 space complexity是个问题，有些问题不需要保存所有中间计算结果的。如果语言级别
提供比较聪明的memoize方式，可以有选择的遗忘，就好办了。
stack overflow的事情很讨厌。by default, stack内存就只有1M，相对现在的机器容
量而言太少了。JVM可以自己调节stack分配大小，从而可以递归很多次。
【在 b******n 的大作中提到】
: memoization啊，clrs里面也有，时间复杂度上没有问题的，
: 最大问题是space complexity，及有可能stack overflow
|
p*****2
发帖数: 21240 | 16
支持大牛。很多时候dfs反而更快
【在 t****a 的大作中提到】
: memoize是相当聪明而且省事的办法。它只算需要算的，复杂度不会比递推高。
: 建议楼主耐心下来把两种方法都做做看以后再下结论。
|
f*********r
发帖数: 85 | 17 计算的overhead在于hash function和hashmap access，这两个忽略的话topdown方法的
复杂度<=bottom up方法的复杂度吧。
★ 发自iPhone App: ChineseWeb 7.8
【在 J*****a 的大作中提到】
: ok 不是指数次 比Dp稍高 但不是指数
|
