|
r*****o
发帖数: 35 | 2 co-qiu DP & any program. paypal. |
|
r*****o
发帖数: 35 | 3 co-qiu DP & any program. paypal. |
|
p*l
发帖数: 241 | 4 【 以下文字转载自 Prose 讨论区 】
发信人: bushijiqiren (爱吃七面鸟的大饼 ), 信区: Prose
标 题: DP要告别美国了
发信站: BBS 未名空间站 (Sat Jan 13 17:43:57 2007)
http://www.bullog.cn/blogs/drunkpiano/archives/23729.aspx
馅饼
drunkpiano @ 2007-1-14 1:26:33 阅读(362) 引用通告 分类: 讲故事
拿一般人的眼光来看，在学业就业方面，我一直是个幸运的人。
初中保送高中，高中保送大学，大学保送研究生。在国内找工作的时候，当时清华某院
本来只招博士生，但我一坨硕士愣是把自己给“忽悠”了进去。出国的时候，人家拼死
拼活努力很多年未必拿到理想的offer，我考G考托写申请材料一共花半年拿到六个
offer。哥大毕业的时候，虽然投的诸多简历石沉大海，但是最后拿到的哈佛博士后
offer，是我最想要的，所以又算是正中下怀。
更重要的是，除了上高中和大学，在上述所有的“成果”中，并没有什么是我真正渴望
和浴血奋战的。一般都是，既然馅饼都 |
|
n******h
发帖数: 50 | 5 DP的idea就是在利用以前的解，空间换时间。如果想要得具体解，倒不必要存储每一组
解，你只需要用指针来track你的解的过程就可以了。 |
|
h**6
发帖数: 4160 | 6 即使用DP，也只是把n!降为2^n*n^2
据说bound and branch很快 |
|
k********n
发帖数: 21 | 7 then how does DP work??
Thanks! |
|
j***n
发帖数: 301 | 8 这题很老了，貌似不是DP。
从最开始做累加，用一个sum变量记录累加结果。再用一个maxsum记录最大值。sum为负
的时候就清零。线性复杂度 |
|
H*X
发帖数: 281 | 9
算是DP吧， 因为position i 的sum是position i-1的sum + array[i], |
|
l******o
发帖数: 144 | 10 O(n)显然是可以做到的。和maximum sum一样，伪DP就可以了。不过maximum sum记录前
面最
大的和，这里要同时记录绝对值最大的正product和负product。Over。
饿，要是谁有我搬板凳 |
|
|
|
|
|
w******0
发帖数: 43 | 15 说明这些公司都太变态了
有几个上班编程序写DP的 |
|
l******c
发帖数: 2555 | 16 computer science changed,
recently, I read a book algorithm
most part are dp and lp.
no sorting algorithm etc |
|
o**********t
发帖数: 406 | 17 DP 是编程的核心技术之一 ...
好像上场踢球，人人都能抡两脚，到一对一的时候，能不能逼真的假动作，有没有人球
分过的本事，就看出谁是球星了。
对了，今年又看世界杯了！！ |
|
f*******r
发帖数: 1086 | 18 今天看了一道DP题目，自己写了一个函数，请大家看看是否有问题:
题目：
A sequence of numbers is called a zig-zag sequence if the differences betwee
n successive numbers strictly alternate between positive and negative. The f
irst difference (if one exists) may be either positive or negative. A sequen
ce with fewer than two elements is trivially a zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3
,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1
,7,4,5,5 are n |
|
|
B*****t
发帖数: 335 | 20 可以用堆来做，复杂度O(nlogk)
这题overlapping 的subproblems不好定义，DP好像不是很适合
smallest window
you know
have a list
propose an |
|
d****n
发帖数: 233 | 21 Good idea. So the time complexity is O(N*logK)? I was studying DP and
tempted to solve problem by it. For this one, I'm thinking of another way to
solve it. Complexity is O(N*K):
Assuming we sort all the positions into a new array A, where each element A[
i] contains two members (position, word), 0<= position < N, 0<=word < K; the
elements are sorted by the position in ascending order.
Elem {
int position,
int word
}
Elem A[] = sorted Elems by position
Elem B[K]; |
|
D****6
发帖数: 278 | 22 Given a matrix of integers. How to calculate the sum of a sub-matrix.
A sub-matrix is represented by x, y, h, w, where x and y is the position of
the upper-left corner, h is the height, w is the width.
int[][] matrix
int sum(int x, int y, int h, int w){...}
这个谁都会.
之后问如果这个函数会被调用多次,而且用在同一个matrix上, sub-matrix会与之前的
overlap, 怎么优化.
我就说用DP之类的, 把之前结果存下来, 有overlap那部分就直接用.
可具体我也不知道怎么做.
请高手指点下
多谢! |
|
B********n
发帖数: 384 | 23 假设数组是a[i], i = 1..n
如果某些数字的和为sum，有两种情况，或者第n个数字被选，或者第n个数字没有被选
count(n, sum) = count (n-1, sum) + count(n-1, sum-a[n]);
只要用一个二维数组来保存dp状态就可以了 |
|
h********e
发帖数: 1972 | 24 即便DP时间上也快不到哪里去。。没啥用。。这种题随便坐就成 |
|
A*********r
发帖数: 564 | 25 令Ｆ（ｉ，ｊ）表示从范围ｉ．．ｊ中取头或尾能得到的最大ｖａｌｕｅ，
那么
F(i,j)=max { min {F(i+1,j-1), F(i+2,j)}+Vi, min {F(i+1,j-1), F(i,j-2))}+Vj }
第一项是取了ｉ的话，至少能够得到的值（对手可能取剩下的ｉ＋１或者ｊ），第二项
是取了ｊ的话，至少能够得到的值。。
下面这个ｌｉｎｋ的第１０道题，基本上一样吧。。
http://people.csail.mit.edu/bdean/6.046/dp/
denominations
player |
|
p*******n
发帖数: 4824 | 26 我觉得是fresh grad倒还好，你们公司的，进去了以后还真有多少人在用DP啊。。。 |
|
|
h*****g
发帖数: 312 | 28 You have to paint N boards of length {B1, B2, B3… BN}. There are K painters
available and you are also given how much time a painter takes to paint 1
unit of board. You have to get this job done as soon as possible under the
constraints that any painter will only paint continuous sections of board,
say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
用DP 得咋解？ |
|
g***s
发帖数: 3811 | 29 再去仔细看例子。DP其实跟贪心一样，是一种思路；不要去背题。 |
|
g**********y
发帖数: 14569 | 30 要把可以递归的东西拎出来，有时候很困难。你要知道贪心可以解，一般来说离解就不
远了。即使知道DP可以解，甚至看了答案，有时都不是很直观的。
举个topcoder的例子，油漆匠刷条纹，象ABCABCA, 问最少刷几次。我读那code, 关键
的就几行，读了我很久才想明白。 |
|
l***i
发帖数: 1309 | 31 Even those in top 100 in topcoder cannot work out hard dp problems sometimes
. |
|
k*j
发帖数: 153 | 32 网上找来的题目
You are given a pyramid; the numbers for example is 2 on the first level, 3
-1 on the second level, 4 7 8 on the third, etc. How do you calculate the
maximum sub sequence of any path traversing the pyramid?
应该是用DP，目前只能想到O(k^2)的做法,k是level数。有没有比这个更快的做法，多
谢！ |
|
e****i
发帖数: 393 | 33 Don't think this is a DP problem. Look into the optimal substructure
carefully. |
|
l***i
发帖数: 1309 | 34 This is a DP problem and a linear time solution exists, assuming you can use
a linear size space. Since you have O(k^2) numbers, using O(k^2) time seems
acceptable. |
|
|
|
r*******n
发帖数: 266 | 37 也不全对....对任何finite coin set...如果钱数足够大, 解一定是greedy的
但是这个门限要用DP来解 |
|
p*****2
发帖数: 21240 | 38
第一道题，假设coin 是 90, 50, 1
给你100
如果用你的方法就会得到1个90,10个1,一共11个。 如果dp的话就是2个50. |
|
p*****2
发帖数: 21240 | 39
第二道题是我看错了，还是你改了。第二题用dp就是为了防止重复计算的。 |
|
g*********e
发帖数: 14401 | 40
这题DP也是有O(n)解法的啊
max(i)=max sum of sub array ending at i
max(i+1)=MAX（max(i)+array[i+1], array[i+1]) |
|
|
b***u
发帖数: 12010 | 42 greedy难在不知道greedy可以。用dp绕半天浪费时间。greedy关键要能证明能贪
in |
|
q***y
发帖数: 236 | 43 给一个全正数的数组，大小为N。将其分成连续的K段。要求每段的和尽量平均。也就是
最大化最小段的和。这个DP公式怎么列啊？ |
|
p*****2
发帖数: 21240 | 44
没有呀。我去年连DP都不会，面试全fail掉了。 |
|
p*****2
发帖数: 21240 | 45
没有呀。我去年连DP都不会，面试全fail掉了。 |
|
l**b
发帖数: 457 | 46 CLRS上面是不是有一个专门的recursion+cache的叫法？memoization？那个大牛给定义
一下。DP还是好难想出来啊。 |
|
t****a
发帖数: 1212 | 47 楼上的都是大牛，抛砖引玉，介绍介绍偷懒的办法
clojure上面的DP可以用memoize recusion function来做，懒汉专用工具 :)
但是这样的recusion还是有可能stack overflow，怎么办呢？
懒汉的办法就是再构造一个lazy sequence从小到大call过去，就保证了recusion不太
会发生了
这样的话，如果memoize太多东西了可能会out of memory，怎么办呢？
在github有clojure更加高级的memoize package，可以搞些什么先进先出或者动态的换
入换出之类的memoize，在小内存机器上可以避免out of memory problem。 |
|
p*****2
发帖数: 21240 | 48
我觉得说的很准确。跟我理解的一样。没有提到的就是，我觉得DP初始化还是蛮tricky
的。需要点经验。 |
|
d**********x
发帖数: 4083 | 49 poj上遍地都是啊
列状态迁移函数，dp解决问题基本都要属于机械化题目了。。 |
|
a********m
发帖数: 15480 | 50 n维的正常，不一定就难，关键是状态和转移。不过确实一般比较花时间，面试题少见
。需要20多分钟能解决的dp问题应该都比较简单。 |
|
