p*****o 发帖数: 1285 | 1 这两天在专攻DP,慢慢的有了一些理解,在这里写一写,如果领悟正确可以帮跟我一样
挣扎的人省些时间,如果不对正好可以请高手指点。
个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个
LeetCode的问题,Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS,如果两
条路径共享一部分的话,共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜
索的问题,从而达到节省一部分时间的目的。对于这个题目,DP不能提高时间复杂度,
因为这题本来就是NP-complete --不论用什么方法,所有路径都被看一遍才能知道结
果。但是由于prune掉很多不必要的搜索,还是可以提高效率。 |
t**********h 发帖数: 2273 | |
d**u 发帖数: 1065 | 3 首先要判断这个问题能不能用dp来解,也就是是否存在最优子结构。
如果存在最优子结构,那么剩下的就是想出状态转移方程了。 |
p*****o 发帖数: 1285 | 4 哇,看来没有基础还是不行啊,大侠两个词就把我彻底打败了。
【在 d**u 的大作中提到】 : 首先要判断这个问题能不能用dp来解,也就是是否存在最优子结构。 : 如果存在最优子结构,那么剩下的就是想出状态转移方程了。
|
p*****o 发帖数: 1285 | 5 一点都不牛,看你楼下我楼上
【在 t**********h 的大作中提到】 : 牛人啊,膜拜
|
p*****2 发帖数: 21240 | 6 对于这个题目,DP不能提高时间复杂度
这句话有大牛confirm吗? |
r*****e 发帖数: 792 | 7 according to my notes, there are two main types of DP: memoization and
bottom-up.
use a table is the first approach but it's typically slower than bottom-up
based method.
Of course, it is the easiest and maybe the only way to solve a lot of
examples.
【在 p*****o 的大作中提到】 : 这两天在专攻DP,慢慢的有了一些理解,在这里写一写,如果领悟正确可以帮跟我一样 : 挣扎的人省些时间,如果不对正好可以请高手指点。 : 个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个 : LeetCode的问题,Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS,如果两 : 条路径共享一部分的话,共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜 : 索的问题,从而达到节省一部分时间的目的。对于这个题目,DP不能提高时间复杂度, : 因为这题本来就是NP-complete --不论用什么方法,所有路径都被看一遍才能知道结 : 果。但是由于prune掉很多不必要的搜索,还是可以提高效率。
|
p*****o 发帖数: 1285 | 8 For this specific problem (Unique Paths II), how does a bottom-up solution
work? I have tried to use a bottom-up method, but soon lost in the mess.
【在 r*****e 的大作中提到】 : according to my notes, there are two main types of DP: memoization and : bottom-up. : use a table is the first approach but it's typically slower than bottom-up : based method. : Of course, it is the easiest and maybe the only way to solve a lot of : examples.
|
d**********x 发帖数: 4083 | 9 as long as u can figure out the state transfer function...
【在 p*****o 的大作中提到】 : For this specific problem (Unique Paths II), how does a bottom-up solution : work? I have tried to use a bottom-up method, but soon lost in the mess.
|
p*****o 发帖数: 1285 | 10 wow,居然找到了,多谢提醒。
【在 d**********x 的大作中提到】 : as long as u can figure out the state transfer function...
|
|
|
h****e 发帖数: 928 | 11 我觉得CLRS书上DP那一章就讲得很清楚了。那一章后面的题目真是
又臭又长,看清题意都要花不少时间。
DP的题目面试和做Online Judge的主要差别是: 一般面试的时候
由于时间有限,用递归加memoization会好写一些;做Online Judge
的时候,写程序没有时间限制,bottom-up程序运行效率会更高一些,
而且不会担心stack overflow。 |
d**********x 发帖数: 4083 | 12 搞久了之后,还是bottom up的好。。
【在 h****e 的大作中提到】 : 我觉得CLRS书上DP那一章就讲得很清楚了。那一章后面的题目真是 : 又臭又长,看清题意都要花不少时间。 : DP的题目面试和做Online Judge的主要差别是: 一般面试的时候 : 由于时间有限,用递归加memoization会好写一些;做Online Judge : 的时候,写程序没有时间限制,bottom-up程序运行效率会更高一些, : 而且不会担心stack overflow。
|
p*****o 发帖数: 1285 | 13 CLRS是什么书?
【在 h****e 的大作中提到】 : 我觉得CLRS书上DP那一章就讲得很清楚了。那一章后面的题目真是 : 又臭又长,看清题意都要花不少时间。 : DP的题目面试和做Online Judge的主要差别是: 一般面试的时候 : 由于时间有限,用递归加memoization会好写一些;做Online Judge : 的时候,写程序没有时间限制,bottom-up程序运行效率会更高一些, : 而且不会担心stack overflow。
|
p*****2 发帖数: 21240 | 14
不一定吧?看题。
【在 d**********x 的大作中提到】 : 搞久了之后,还是bottom up的好。。
|
p*****o 发帖数: 1285 | 15 这句话我收回了,之前是我榆木脑袋想不到。
【在 p*****2 的大作中提到】 : 对于这个题目,DP不能提高时间复杂度 : 这句话有大牛confirm吗?
|
h****e 发帖数: 928 | 16 Introduction to Algorithms from MIT,CLRS是四位作者姓的首字母。
大概是一本永远看不完的书。
【在 p*****o 的大作中提到】 : CLRS是什么书?
|
p*****2 发帖数: 21240 | 17
我翻了翻,但啥也没记住呀。
【在 h****e 的大作中提到】 : Introduction to Algorithms from MIT,CLRS是四位作者姓的首字母。 : 大概是一本永远看不完的书。
|
h****e 发帖数: 928 | 18 你看的是第三版的吗?第15.3节讲可以用DP的必要元素以及解决办法。
当然具体题目发现那些要素并不是容易的事情。我也只是看了纸上谈兵
而已。
【在 p*****2 的大作中提到】 : : 我翻了翻,但啥也没记住呀。
|
d**********x 发帖数: 4083 | 19 不是题目的问题
应用中bottom up的会快。。
【在 p*****2 的大作中提到】 : : 我翻了翻,但啥也没记住呀。
|
p*****2 发帖数: 21240 | 20
你看看GCJ Round1 最后一题 bottom up怎么搞?
【在 d**********x 的大作中提到】 : 不是题目的问题 : 应用中bottom up的会快。。
|
|
|
p*****2 发帖数: 21240 | 21
我脑子太笨了, CLRS, programming pearls, careerup 150全买了。啥都没学会。
【在 h****e 的大作中提到】 : 你看的是第三版的吗?第15.3节讲可以用DP的必要元素以及解决办法。 : 当然具体题目发现那些要素并不是容易的事情。我也只是看了纸上谈兵 : 而已。
|
l******s 发帖数: 3045 | 22 我觉得您可以去试试水啦,现在是版面众望所归
【在 p*****2 的大作中提到】 : : 我脑子太笨了, CLRS, programming pearls, careerup 150全买了。啥都没学会。
|
d**********x 发帖数: 4083 | 23 粗看起来和最长公共子序列或者edit distance没有区别
有啥陷阱么。。?
【在 p*****2 的大作中提到】 : : 我脑子太笨了, CLRS, programming pearls, careerup 150全买了。啥都没学会。
|
X*K 发帖数: 87 | 24 这个Unique Paths II怎么变成NP-complete了,不是把二维数组过一遍,
复杂度O(mn)吗?
【在 p*****o 的大作中提到】 : 这两天在专攻DP,慢慢的有了一些理解,在这里写一写,如果领悟正确可以帮跟我一样 : 挣扎的人省些时间,如果不对正好可以请高手指点。 : 个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个 : LeetCode的问题,Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS,如果两 : 条路径共享一部分的话,共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜 : 索的问题,从而达到节省一部分时间的目的。对于这个题目,DP不能提高时间复杂度, : 因为这题本来就是NP-complete --不论用什么方法,所有路径都被看一遍才能知道结 : 果。但是由于prune掉很多不必要的搜索,还是可以提高效率。
|
p*****o 发帖数: 1285 | 25 我不一开始没想到么,看后来更新。
【在 X*K 的大作中提到】 : 这个Unique Paths II怎么变成NP-complete了,不是把二维数组过一遍, : 复杂度O(mn)吗?
|