由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - dynamical programming
相关主题
自己总结了下什么时候用dp(循环),什么时候用递归enumerate all unique paths of robot
刚开始找工作,算法要看什么书啊?offer报告 (附带找工作感言)
带限制条件的最短路径题怎么做?[面试题] 如何打印一个二叉树level by level?
为什么我觉得dp的题都挺难的检查graph里面是否有circle,是用BFS,还是DFS?
一道G题rejected by facebook after 2nd phone interview
shortest path in matrix问一道少见的微软面试题。
Print all paths from root to leafs in a binary tree问一道字符串相关的题目。
DP感受 (高手请绕行)面试问题请教:如何在字典中得到最长的复合词
相关话题的讨论汇总
话题: dp话题: dynamical话题: bottom话题: clrs
进入JobHunting版参与讨论
1 (共1页)
p*****o
发帖数: 1285
1
这两天在专攻DP,慢慢的有了一些理解,在这里写一写,如果领悟正确可以帮跟我一样
挣扎的人省些时间,如果不对正好可以请高手指点。
个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个
LeetCode的问题,Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS,如果两
条路径共享一部分的话,共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜
索的问题,从而达到节省一部分时间的目的。对于这个题目,DP不能提高时间复杂度,
因为这题本来就是NP-complete --不论用什么方法,所有路径都被看一遍才能知道结
果。但是由于prune掉很多不必要的搜索,还是可以提高效率。
t**********h
发帖数: 2273
2
牛人啊,膜拜
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...
相关主题
shortest path in matrixenumerate all unique paths of robot
Print all paths from root to leafs in a binary treeoffer报告 (附带找工作感言)
DP感受 (高手请绕行)[面试题] 如何打印一个二叉树level by level?
进入JobHunting版参与讨论
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的会快。。

相关主题
检查graph里面是否有circle,是用BFS,还是DFS?问一道字符串相关的题目。
rejected by facebook after 2nd phone interview面试问题请教:如何在字典中得到最长的复合词
问一道少见的微软面试题。DFS vs. BFS in Web Crawling
进入JobHunting版参与讨论
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)吗?

1 (共1页)
进入JobHunting版参与讨论
相关主题
面试问题请教:如何在字典中得到最长的复合词一道G题
DFS vs. BFS in Web Crawlingshortest path in matrix
请教一道题Print all paths from root to leafs in a binary tree
一道google电面题,估计挂了。。。DP感受 (高手请绕行)
自己总结了下什么时候用dp(循环),什么时候用递归enumerate all unique paths of robot
刚开始找工作,算法要看什么书啊?offer报告 (附带找工作感言)
带限制条件的最短路径题怎么做?[面试题] 如何打印一个二叉树level by level?
为什么我觉得dp的题都挺难的检查graph里面是否有circle,是用BFS,还是DFS?
相关话题的讨论汇总
话题: dp话题: dynamical话题: bottom话题: clrs