由买买提看人间百态

topics

全部话题 - 话题: dp
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
p*****2
发帖数: 21240
1
来自主题: JobHunting版 - 关于DP的问题
不好意思。又看错了。你提到O(n)的解法。
我认为这题O(n)的解法是好的。但是这也是一道典型的dp题。如果你在比赛中,用dp来
解比你用那个O(n)的要简单多了。如果面试中,就是考察那个O(n)的算法了。目的不一
样。
q****x
发帖数: 7404
2
来自主题: JobHunting版 - 关于DP的问题

贪心法,应该有反例。dp经典题。
这个算不算dp两可。
O******i
发帖数: 269
3
来自主题: JobHunting版 - DP感受 (高手请绕行)
DP就是利用一维或者二维的数组,找递推关系式,也就是状态转移方程。常数空间和三
维以上空间在实际面试中不多见。
难就难在写出递归方程。
不用说背包问题,就连经典的扔鸡蛋题(虽然有巧妙的小学生算法, 1+2+...+14恰好刚
大于100)本质也是DP。
O******i
发帖数: 269
4
来自主题: JobHunting版 - DP感受 (高手请绕行)
最简单的DP,就是兔子问题的Fibonacci数列。
次简单的是二项式定理的组合数公式,也就是贾宪三角,杨辉三角,帕斯卡三角。每个
数等于肩膀上两个数的和。
那个leetcode的题,从矩阵左上角走到右下角的不同走法,中学生直接写出组合数的解
。而求组合数的值除了直接用公式,就是用杨辉三角。那题的DP解法,实际上就是在暗
中进行杨辉三角的迭代。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
O******i
发帖数: 269
5
来自主题: JobHunting版 - DP感受 (高手请绕行)
最霸气的DP是三维以上的,也只有ACM的张驰这类牛人才得心应手,堪比侍魂中的天霸
封神斩。一般的DP面试,能发出奥义弧月斩就够用了。
F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
则如果存在k,使得要么
1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
F[l1 + k][u1][l2 + k][u2]
2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
F[l1 + k][u1][l2][l2 + k - 1]
两者有一个真,则F[l1][u1][l2][u2]为真
因为l1, u1, l2确定,则u2 = u1 - l1 + l2,所以状态总数为n^3
决策为o(n), 总复杂度o(N^4)
a********m
发帖数: 15480
6
来自主题: JobHunting版 - DP感受 (高手请绕行)
不错。赞。
dp定义确实有点混乱。俺也是从careerup开始真正学,所以以前经常把top-down算dp,
bottom-up不算。现在习惯了,不管3728全算。反正思路是一样的。
O******i
发帖数: 269
7
来自主题: JobHunting版 - DP感受 (高手请绕行)
为什么是先看CC而且相信它的定义呢?
如果先看CLRS(有一章专门讲DP,还是期末必考的),再看CC,就会觉得CC只把DP定义为
top-down的recursion + cache挺误导的。
c********t
发帖数: 5706
8
来自主题: JobHunting版 - DP感受 (高手请绕行)
顶!
如果看到题很快能想到应该用DP,但却怎么也写不出DP公式,怎么提高?是不是数学基
础太差?
t****a
发帖数: 1212
9
来自主题: JobHunting版 - DP感受 (高手请绕行)
对了,还有另外一个偷懒的技巧
有些DP可以转化为ILP(整数/布尔线性规划)。对于这类题目只要列出约束和目标方程
,直接call gnu的ILP package就可以拿到最优解,程序都不用写了~
版上以前的一些DP题目就可以直接这样用R来解决的,比如背包啦,换硬币,3sum,
4sum之类的
这样的code其实是更加stable更容易维护。就是不知道面试时候这样搞面试官买不买帐
t****a
发帖数: 1212
10
来自主题: JobHunting版 - DP感受 (高手请绕行)
ILP在问题规模大的时候会挂掉。不过DP也是一样会挂的。我经验不多,不过还是感觉
ILP要比DP快一些,而且程序明显容易写和修改。
a********m
发帖数: 15480
11
来自主题: JobHunting版 - DP感受 (高手请绕行)
dp计算本身和brute force没大区别,只是复杂度提高而且是可以计算出来的,只要公
式对资源够,不可能挂。LP印象中是逼近为基础的吧,约束条件也不是那么容易写和修
改的。
快不快看情况了,dp多数容易问题都是o(n)到o(n^2)。当然特别复杂的不好说了。
z**x
发帖数: 16
12
来自主题: JobHunting版 - Another DP Problem: Balanced Partition
我的想法是:
1.设上限为 sum(1,n)/2
2.背包DP,求出子集A,such that for all possible subset A, ( sum(1,n)/2- A.sum
) is minimized
3.所以有A的补集B, ( B.sum-sum(1,n)/2)is minimized
4.所以对于这个partition, |A.sum - B.sum| is minimized
另外想请问背包问题的DP解法的前提是要保证物品的weight要不小于零吗(如本题的O
到K),另外这个上限K有没有实际的作用呢
p*****2
发帖数: 21240
13
来自主题: JobHunting版 - 怎么准备recursion 和 dp 题?
recursion还好吧?recursion的DP也好好吧?
我觉得难的是iteration的DP。
t*********7
发帖数: 255
14
来自主题: JobHunting版 - 什么是DP?:)
VP,MANAGER,S-VP...各种UP头衔的,几个懂DP的,DP就是码工的象征啊
j*****l
发帖数: 1624
15
来自主题: JobHunting版 - 什么是DP?:)
google简直是超级无敌的贴心,叫我去onsite的邮件里还发了好多link叫我照着那些
link好好准备。那就是考试范围。
这是他家给我发的dp的link
http://people.csail.mit.edu/bdean/6.046/dp/
K*******i
发帖数: 399
16
来自主题: JobHunting版 - 这道硬币找零题有好的DP解法么?
有25分,10分,5分和1分四种硬币,假定每种硬币都有无限个。给定一个找零的分值N,求不同的找法。递归比较容易,那么如何用DP?
比如说N = 11,共四种找法:
10 * 1 + 1 * 1
5 * 2 + 1 * 1
5 * 1 + 1 * 6
1 * 11
想用DP,状态转移方程如下
F(0) = 1;
F(n) = {F(n - 25), n >= 25} + {F(n - 10), n >= 10} + {F(n - 5), n >= 5} + {F(n - 1), n >= 1}
也就是
F(11) = F(1) + F(6) + F(10)
但是却发现有重复
F(6)的解包含5 * 1 + 1 * 1
在这基础上添加一个五分硬币得到5 * 2 + 1 * 1
F(10)的解包含5 * 2
在这基础上添加一个一分硬币得到5 * 2 + 1 * 1
这样就重复计算了
p*****2
发帖数: 21240
17
来自主题: JobHunting版 - 这道硬币找零题有好的DP解法么?
先用recursion+cache的DP,再想bottom up的DP应该就会容易了。
p*****2
发帖数: 21240
18

dp
靠。语文老师自己一定位,别人谁还敢说话呢?我觉得DP高深莫测,我是真不懂。
g*********e
发帖数: 14401
19
偶是半路出家的 懂的很少
当时上算法课,就觉得对DP特有感觉,就像解中学数学的题目那种感觉。
DP主要是寻找递推公式,看到题目,凭着经验多试试一般都会有些思路的。
g*********e
发帖数: 14401
20
没有刻意练过,觉得DP的思路其实挺清晰的,就是解决小问题,然后找递推。不像一些
O(n)复杂度的问题那么tricky。DP对复杂度的要求也很低,通常是polinomial的。
另外,我看的书是algorithm design by Jon Kleinberg, Cornell.
C***U
发帖数: 2406
21
这题DP的意义不大吧。。。
DP的空间占用会很大吧
b*****o
发帖数: 715
22
来自主题: JobHunting版 - 究竟什么定义了DP
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
g****y
发帖数: 240
23
来自主题: JobHunting版 - 究竟什么定义了DP
DP 用recursion也可以,那就是top down。一般都用iteration,也就是bottom up。
Programming其实是table的意思。所以DP可以理解为你是否用table记录了subproblem
的结果。
g****y
发帖数: 240
24
就说之前研究过,是经典DP问题,直接上DP。
f*****e
发帖数: 2992
25
来自主题: JobHunting版 - 这道题DP怎么做阿
是啊,d[i,i+1]也可以用DP算的,总而言之,这个题用DP算了两个量吧,一个量min_j用
到了另一个量d(j-1,j),有时min_j=d(j-1,j) (当j-1,j在不同partition的时候),最
终的min_j就是所求。
g*********e
发帖数: 14401
26
来自主题: JobHunting版 - 感觉leetcode的OJ有点太偏重DP了
几乎有一半是DP的题目。
实际面试中,问到DP的其实并不多,实际工作中用到的更少。
p*****2
发帖数: 21240
27
来自主题: JobHunting版 - 感觉leetcode的OJ有点太偏重DP了
DP题目以前很少。后来我总是碰到,就加进去了。现在DP题比较全面一些了。
p*****2
发帖数: 21240
28
来自主题: JobHunting版 - 感觉leetcode的OJ有点太偏重DP了

其实DP只是一种解法。很多题不用DP也能解。
e***s
发帖数: 799
29
一个连续没空格字符串,一个字典,怎样知道最少单词的分割方法?
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
这是一个很好的POST,但是没有提供DP的方法。不知道这个递归的memorization算不算
DP?
多谢了!
方法定义
String segmentString(String s, Set dict)
例如
"applepie" -> "apple pie" 当然字典里面没有 "applepie" 这个字咯
O******i
发帖数: 269
30
这题在CAIWU的G面经也有?
和一个老美。先上来DP问题。说给一个字符串,是通过一些单词没有空格隔开的。让我
如果把他们分成最少的单词数。用了DP做出来。不过不知道他听懂没有。然后让设计一
个数据结构,使得一个人输入几个字母以后,会弹出来推荐的词。我用了prefix tree
。然后他问怎么能最小化打字。我就说可以根据概率来弹出后面3个的推荐,然后一次
继续。然后在这个上面纠缠了很多,然后考虑了很多情况。然后算了一下期望可以减少
的打字数。
c********r
发帖数: 286
31
来自主题: JobHunting版 - Leetcode上DP的那些事儿
请问大牛门,Leetcode上除了edit distance, unique path, minimum path...
whatever path
还有哪些可以用DP解的呢? 想多练习一下thinking in DP,望大牛们指教 :)
c********t
发帖数: 5706
32
来自主题: JobHunting版 - Leetcode上DP的那些事儿
赞!
怎么会这么多dp? 是不是用得太狠了?B n s stock I 也要 dp?

★ 发自iPhone App: ChineseWeb 7.8
f*********m
发帖数: 726
33
这里说的是概念上的Tree。
若把整个大问题放在root,可以用DP解决的问题会有很多重复的subtree。除了这些还
有别的区别吗,尤其是(概念上)构建tree的时候?
比如说,是按照从左到右(从小问题到大问题)构建好(即,把小问题放在tree的高层
,把最后的大问题放在叶子),还是从右到左构建好(即,把大问题放在高层)?有没
有比较好的通用策略?
p*****2
发帖数: 21240
34
来自主题: JobHunting版 - 通过思考DP又让我明白了一件事情
我学过的所有语言里我最喜欢Ruby了,主要的原因是感觉很灵活,但是没有往深层次上
去想为什么灵活。这次思考DP突然给想明白了。
首先,DP里面很多东西都是很boring的,都是弥补语言缺陷的。而我也分析了面向过程
,面向对象,函数编程各有优缺点
http://blog.sina.com.cn/s/blog_b9285de20101jzrn.html
也就是说很多pattern是在特点的编程模式,或者编程语言才会出现的。而Ruby是面向
过程,面向对象和函数编程三位一体集大成的语言,自然就变的很灵活了,而你也不需
要拘泥于模式了。实在是一门神奇的语言。
用不用Ruby是一回事,但是感觉平生不曾学Ruby,即使程序员也枉然呀。
还有人说编程语言会一两门就够了,我看不一定。不多学几门语言很难融会贯通呀。
p*****2
发帖数: 21240
35
来自主题: JobHunting版 - 通过思考DP又让我明白了一件事情

现在是从DP的角度去讨论语言的。跟多线程没什么关系。如果说效率的话,DP都会使效
率下降,因为多加了layer了。
J*****a
发帖数: 4262
36
不是啊 她还是按递归那个顺序算
比如背包问题 dp的矩阵应该一行一行的算 矩阵每个元素只要遍历一次
比如断字问题 就应该先算对角线 向左上方向遍历
而且DP都是先算小子问题 在算大子问题 顺序都是精心安排才能最大限度降复杂度
但是她还是按照递归算法访问那些子问题 所以先碰到的是大问题 因此就肯定有很多
mismatch (在hashtable里找不到) 所以复杂度肯定高了啊
s**********1
发帖数: 58
37
那个本来也是DP,用MEMO实现的DP,实现方式不同而已,而且这种写起来简单,在有些
情况下还能避免求解无用的子问题。lz可能只是以前没见过这个吧,没问题的。但是那
本书本身质量不高是真的。
b******7
发帖数: 92
38
同意shaoshuai321。
memoization方式处理DP问题,这样可以让DP按top-down的方式递归实现。
在有些bottom-up方式难处理的场合,用这种技术可以很方便的写出code。
比如个人认为这个题用memoization难度会降低很多,也容易bug free
http://www.geeksforgeeks.org/largest-independent-set-problem/
p*****2
发帖数: 21240
39
作者对DP的理解局限了。不过她的理解对于初学DP也算是挺有用的。面试这么干也可以
。更容易bug free。
J*****a
发帖数: 4262
40
er。。。。
我还是持保留意见
比如17.14的答案就有问题,而且她的所谓dp算法复杂度明显比传统Bottom up的DP高(
有指数次递归调用)
w***y
发帖数: 6251
41
来自主题: JobHunting版 - 要开始啃DP这块硬骨头了
我上次看的是这个
http://people.csail.mit.edu/bdean/6.046/dp/
leetcode上也有不少,虽然很多问题都是,我看到了压根想不到dp :((
z*******a
发帖数: 858
42
学文科出身,只是因为为了混口饭吃所以才干CS这行。
可能跟版上绝大多数人资质都相反:理解能力非常差,记忆能力超强。
面试C++、Java语言特性、Design Pattern之类完全不惧,因为都背好了,我也不知道
自己说的是什么,不过知道按照背的讲出来,一般面试的都会很满意,因为我连例子都
背出来了。偶尔被识破,不过几率很低很低。
算法不太好弄,也就背到能混过Microsoft面试这个水平。再往上,比如Google
Linkedin 这个级别就歇了,主要是有的DP、图题看过很多遍还是记不住,而且FLG等写
Code要求比较高(我写Code还是相对弱的),也许用功不够多。
主要是,CS背景比较弱,平时一忙或是一懒,就很容易懈怠,没有能力静下心来潜心研
究(其实是从头学习);碰到面试了便祭出死记硬背大法,因为短平快。
问题是,DP、图论这些题一方面难度高,另一方面更灵活一点。我究竟是该继续靠死记
硬背呢?还是多看书、从头开始理解?
s********i
发帖数: 145
43
"算法不太好弄,也就背到能混过Microsoft面试这个水平" Microsoft 真是躺着都中枪
啊...
Just some crude thoughts...
DP如果不好理解,但是recursion应该好理解吧, 把DP想成cached recursion就行了。
不完全正确,但是肯定比你背题要好...
图论其实考得不多吧,理解图的几种表达方式以及优缺点,然后把深度/广度优先搜索/
遍历理解了,其他的更复杂的算法慢慢就能理解了。
p*****2
发帖数: 21240
44
来自主题: JobHunting版 - 面试 DP题也要求 bugfree吗?

嗯。DP的难点主要是这个,倒不是coding。当然有些DP coding也比较麻烦。
x*********w
发帖数: 533
45
来自主题: JobHunting版 - 请教一道rocket fuel DP题
想了一个实现起来超复杂的。
建立一个4维dp matrix. dp[i][j][k][l]为坐标矩阵(i,j), (k,l)的最优解
for (l = 1; l <= max_l; l++) //长度递增
{
for (w = 1; w <= max_w; w++) //宽度递增
{
对每一个sub matrix (max_w*max_w*max_l*max_l 个)
{
如果在一个大矩阵中挖去了一个小矩阵,会把剩下的空间分成8块小的
matrix
取所有可能组合的max value,考虑横跨各种两个小矩阵的情况
}
}
}
s*******s
发帖数: 1031
46
来自主题: JobHunting版 - 请教一道rocket fuel DP题
就是那个cut rope的二维扩展。用DP来做。
int getPrice(int L, int W, vector > pieces) {
int vector > M(L+1, vector(W+1, 0));
/*
Use DP.
For , cut the pieces from the left top corner we c
an get three sub-problems:
(1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
(2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
*/
for(int i=0; i<=L; ++i) {
for(int j=0; j ... 阅读全帖
x*********w
发帖数: 533
47
来自主题: JobHunting版 - 请教一道rocket fuel DP题
想了一个实现起来超复杂的。
建立一个4维dp matrix. dp[i][j][k][l]为坐标矩阵(i,j), (k,l)的最优解
for (l = 1; l <= max_l; l++) //长度递增
{
for (w = 1; w <= max_w; w++) //宽度递增
{
对每一个sub matrix (max_w*max_w*max_l*max_l 个)
{
如果在一个大矩阵中挖去了一个小矩阵,会把剩下的空间分成8块小的
matrix
取所有可能组合的max value,考虑横跨各种两个小矩阵的情况
}
}
}
s*******s
发帖数: 1031
48
来自主题: JobHunting版 - 请教一道rocket fuel DP题
就是那个cut rope的二维扩展。用DP来做。
int getPrice(int L, int W, vector > pieces) {
int vector > M(L+1, vector(W+1, 0));
/*
Use DP.
For , cut the pieces from the left top corner we c
an get three sub-problems:
(1). getPrice(L-l(k), W, prices) & getPrice(l(k), W-w(k), prices)
(2). getPrice(L, W-w(k), prices) & getPrice(L-l(k), w(k), prices)
*/
for(int i=0; i<=L; ++i) {
for(int j=0; j ... 阅读全帖
r**********g
发帖数: 22734
49
来自主题: JobHunting版 - 不会DP是不是找不到工作?
我每天都在DP,日夜研究DP,各种各样的,为啥拿不到30万……
i********s
发帖数: 22
50
这个题目比较恶心,O(N*N)超内存,直接DP超时。
我在DP基础上做了一个长度剪枝,通过大数据,感觉是OJ上有些比较tricky的case;
附上我的解答;
https://github.com/xiongjunliang/leetcode/blob/master/wildcardmatch/
wildcardmatch2.cpp
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)