j******2
发帖数: 362 | 1 一直以为DP就是store了之前结果的recursion。但是看到150第五版里，把18.12（最大
和的submatrix）归为DP&recursion（在9章末提到）。18.12显然没有递归，是在
iteratively利用之前的结果。所以是否DP就是recursion or iteration with stored
results?
但是18.11（最大的黑边square）里面，第二种方法把右、下的黑像素个数存储起来的
过程，跟18.12非常相似啊，iteratively using previous results，但是却没有算成
DP。
所以DP的特征究竟是什么？ |
b*****o
发帖数: 715 | 2 iteration != recursion.
Take a very simple example of computing Fibonacci array:
(1) This is recursion, but NOT DP:
int fib(int n) {
if (n <= 2) {
return 1;
}
return fib(n-1) + fib(n-2);
}
(2) This is DP:
int fib_dp(int n) {
int a = 1;
int b = 1;
int sum;
for (int i=0;i
sum = a + b;
a = b;
b = sum;
}
return sum;
}
stored
【在 j******2 的大作中提到】
: 一直以为DP就是store了之前结果的recursion。但是看到150第五版里，把18.12（最大
: 和的submatrix）归为DP&recursion（在9章末提到）。18.12显然没有递归，是在
: iteratively利用之前的结果。所以是否DP就是recursion or iteration with stored
: results?
: 但是18.11（最大的黑边square）里面，第二种方法把右、下的黑像素个数存储起来的
: 过程，跟18.12非常相似啊，iteratively using previous results，但是却没有算成
: DP。
: 所以DP的特征究竟是什么？
|
j******2
发帖数: 362 | 3 thanks!
that's what i mean.
所以DP不一定要有recursion＋using previous results
iteration+using previous results 也算。
【在 b*****o 的大作中提到】
: iteration != recursion.
: Take a very simple example of computing Fibonacci array:
: (1) This is recursion, but NOT DP:
: int fib(int n) {
: if (n <= 2) {
: return 1;
: }
: return fib(n-1) + fib(n-2);
: }
: (2) This is DP:
|
p*****2
发帖数: 21240 | |
i*********7
发帖数: 348 | 5 我看clrs的DP里面，其实大部分recursion都最终转为iteration（貌似是效率更高的原
因） |
g****y
发帖数: 240 | 6 DP 用recursion也可以，那就是top down。一般都用iteration，也就是bottom up。
Programming其实是table的意思。所以DP可以理解为你是否用table记录了subproblem
的结果。 |
j******2
发帖数: 362 | 7 清楚了！
谢谢！
subproblem
【在 g****y 的大作中提到】
: DP 用recursion也可以，那就是top down。一般都用iteration，也就是bottom up。
: Programming其实是table的意思。所以DP可以理解为你是否用table记录了subproblem
: 的结果。
|
j******2
发帖数: 362 | 8 那18.11（找最大黑边subsquare中的preprocess）一定也是DP了，只是书里没这么归纳。
有人confirm一下吗？ |
S********t
发帖数: 3431 | 9 两个词，optimal substructure
stored
【在 j******2 的大作中提到】
: 一直以为DP就是store了之前结果的recursion。但是看到150第五版里，把18.12（最大
: 和的submatrix）归为DP&recursion（在9章末提到）。18.12显然没有递归，是在
: iteratively利用之前的结果。所以是否DP就是recursion or iteration with stored
: results?
: 但是18.11（最大的黑边square）里面，第二种方法把右、下的黑像素个数存储起来的
: 过程，跟18.12非常相似啊，iteratively using previous results，但是却没有算成
: DP。
: 所以DP的特征究竟是什么？
|
r*****e
发帖数: 264 | |
|
|
g****y
发帖数: 240 | 11 18.11 不是DP。
pre_processing的过程是DP，但是主程序不是DP，就是一般的brute force。
纳。
【在 j******2 的大作中提到】
: 那18.11（找最大黑边subsquare中的preprocess）一定也是DP了，只是书里没这么归纳。
: 有人confirm一下吗？
|
j******2
发帖数: 362 | 12 谢谢你答我。我就是说的preprocess是DP。看来我还是理解对了的哈。
【在 g****y 的大作中提到】
: 18.11 不是DP。
: pre_processing的过程是DP，但是主程序不是DP，就是一般的brute force。
:
: 纳。
|
d**********x
发帖数: 4083 | 13 最优子问题
stored
【在 j******2 的大作中提到】
: 一直以为DP就是store了之前结果的recursion。但是看到150第五版里，把18.12（最大
: 和的submatrix）归为DP&recursion（在9章末提到）。18.12显然没有递归，是在
: iteratively利用之前的结果。所以是否DP就是recursion or iteration with stored
: results?
: 但是18.11（最大的黑边square）里面，第二种方法把右、下的黑像素个数存储起来的
: 过程，跟18.12非常相似啊，iteratively using previous results，但是却没有算成
: DP。
: 所以DP的特征究竟是什么？
|
j******2
发帖数: 362 | 14 想着想着又有点糊涂了。DP的精髓究竟是1.存储先前结果，还是2.利用最优子问题解决
现有最优问题？
如CLRS及devilphoenix所说，DP的关键2.，但是这样的话，经典DP fibonacci有什么最
优选择可言啊？不就是存储先前结果吗？
18.11（最小黑边框）的preprocess也很像fibonacci的情况，一步步存结果，累加，没
有选择出现。
如果fibonacci算DP，那很多iteration和recursion凡是利用了前面结果的是不是都要
算DP啊？比如string permutation.
【在 g****y 的大作中提到】
: 18.11 不是DP。
: pre_processing的过程是DP，但是主程序不是DP，就是一般的brute force。
:
: 纳。
|
S*********r
发帖数: 4729 | 15 显然答案是2。其次，解决最优子问题一般都是用greedy方法从候选中挑一个最好的。
fb我不觉得算dp。
【在 j******2 的大作中提到】
: 想着想着又有点糊涂了。DP的精髓究竟是1.存储先前结果，还是2.利用最优子问题解决
: 现有最优问题？
: 如CLRS及devilphoenix所说，DP的关键2.，但是这样的话，经典DP fibonacci有什么最
: 优选择可言啊？不就是存储先前结果吗？
: 18.11（最小黑边框）的preprocess也很像fibonacci的情况，一步步存结果，累加，没
: 有选择出现。
: 如果fibonacci算DP，那很多iteration和recursion凡是利用了前面结果的是不是都要
: 算DP啊？比如string permutation.
|
j******2
发帖数: 362 | 16 那就是说，DP问题必须是最优化问题。像在有路障的格子中找有多少种路径，一个
boolean expression有几种打括号以得到true，8皇后，running up stairs...这样
count ways的题，就都不可能是DP了，只能算是有memoization的recursion
按照最优化子问题的标准，150这本书的第九章，Dynamic Programming and Recursion
里的11个问题没有一个是符合的。只有17、18章有两题算DP。
【在 S*********r 的大作中提到】
: 显然答案是2。其次，解决最优子问题一般都是用greedy方法从候选中挑一个最好的。
: fb我不觉得算dp。
|
S*********r
发帖数: 4729 | 17 你说的很多是greedy方法。DP经常用greedy方法解决子问题。所以这两个概念比较容易
混淆。
不过，话说回来，你只要知道怎么解决实际问题就行 没必要硬记得这些概念吧
Recursion
【在 j******2 的大作中提到】
: 那就是说，DP问题必须是最优化问题。像在有路障的格子中找有多少种路径，一个
: boolean expression有几种打括号以得到true，8皇后，running up stairs...这样
: count ways的题，就都不可能是DP了，只能算是有memoization的recursion
: 按照最优化子问题的标准，150这本书的第九章，Dynamic Programming and Recursion
: 里的11个问题没有一个是符合的。只有17、18章有两题算DP。
|
a********m
发帖数: 15480 | 18 当然是2，因为2所以才能有1呀。要是2不符合，1存了也没有用。
【在 j******2 的大作中提到】
: 想着想着又有点糊涂了。DP的精髓究竟是1.存储先前结果，还是2.利用最优子问题解决
: 现有最优问题？
: 如CLRS及devilphoenix所说，DP的关键2.，但是这样的话，经典DP fibonacci有什么最
: 优选择可言啊？不就是存储先前结果吗？
: 18.11（最小黑边框）的preprocess也很像fibonacci的情况，一步步存结果，累加，没
: 有选择出现。
: 如果fibonacci算DP，那很多iteration和recursion凡是利用了前面结果的是不是都要
: 算DP啊？比如string permutation.
|
j******2
发帖数: 362 | 19 不好意思，确实有点钻牛角尖了。因为没学过所以看了看CLRS一不小心跑题了。
再啰嗦一句，CLRS讲Greedy同DP一样最关键要素是optimal structure for subproblem
，只是greedy先make a choice for this step,再解决subproblem;DP则要根据子问题
来make current choice。所以我觉得所有“求有几种。。。解法”的问题都不是最优
化问题，都不算DP或Greedy。
还是回到正轨继续做题。
【在 S*********r 的大作中提到】
: 你说的很多是greedy方法。DP经常用greedy方法解决子问题。所以这两个概念比较容易
: 混淆。
: 不过，话说回来，你只要知道怎么解决实际问题就行 没必要硬记得这些概念吧
:
: Recursion
|
