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)吗？
|
