由买买提看人间百态

topics

全部话题 - 话题: dp
首页 上页 1 2 3 4 5 6 7 8 9 10 (共10页)
b********r
发帖数: 1257
1
来自主题: GiftCard版 - 求购DP&EPG
co-qiu DP any program
r*****o
发帖数: 35
2
来自主题: GiftCard版 - 求购DP&EPG
co-qiu DP & any program. paypal.
r*****o
发帖数: 35
3
来自主题: GiftCard版 - 求购DP&EPG
co-qiu DP & any program. paypal.
p*l
发帖数: 241
4
来自主题: JobHunting版 - DP要告别美国了 (转载)
【 以下文字转载自 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
来自主题: JobHunting版 - 关于DP问题请教。
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
来自主题: JobHunting版 - 问道微软面试DP题
这题很老了,貌似不是DP。
从最开始做累加,用一个sum变量记录累加结果。再用一个maxsum记录最大值。sum为负
的时候就清零。线性复杂度
H*X
发帖数: 281
9
来自主题: JobHunting版 - 问道微软面试DP题

算是DP吧, 因为position i 的sum是position i-1的sum + array[i],
l******o
发帖数: 144
10
来自主题: JobHunting版 - 问道微软面试DP题
O(n)显然是可以做到的。和maximum sum一样,伪DP就可以了。不过maximum sum记录前
面最
大的和,这里要同时记录绝对值最大的正product和负product。Over。

饿,要是谁有我搬板凳
c***p
发帖数: 221
11
来自主题: JobHunting版 - DP怎么搞,学不太会啊
MIT 的opencourseware 的introduction to algorithms 有一节讲 DP:
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed15.htm
c***p
发帖数: 221
x****g
发帖数: 2000
13
来自主题: JobHunting版 - 现在满版的DP
啥叫DP
m*****g
发帖数: 226
14
来自主题: JobHunting版 - 现在满版的DP
我去微软面试,全部都是DP
当场被搞死
w******0
发帖数: 43
15
来自主题: JobHunting版 - 现在满版的DP
说明这些公司都太变态了
有几个上班编程序写DP的
l******c
发帖数: 2555
16
来自主题: JobHunting版 - 现在满版的DP
computer science changed,
recently, I read a book algorithm
most part are dp and lp.
no sorting algorithm etc
o**********t
发帖数: 406
17
来自主题: JobHunting版 - 现在满版的DP
DP 是编程的核心技术之一 ...
好像上场踢球,人人都能抡两脚,到一对一的时候,能不能逼真的假动作,有没有人球
分过的本事,就看出谁是球星了。
对了,今年又看世界杯了!!
f*******r
发帖数: 1086
18
来自主题: JobHunting版 - 问一道简单DP题
今天看了一道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
K******g
发帖数: 1870
19
来自主题: JobHunting版 - 问一道简单DP题
这个不需要DP吧?
B*****t
发帖数: 335
20
来自主题: JobHunting版 - Is this a DP problem?
可以用堆来做,复杂度O(nlogk)
这题overlapping 的subproblems不好定义,DP好像不是很适合

smallest window
you know
have a list
propose an
d****n
发帖数: 233
21
来自主题: JobHunting版 - Is this a DP problem?
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
来自主题: JobHunting版 - 一道 Amazon DP题
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
来自主题: JobHunting版 - 请教一个DP的问题
假设数组是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
来自主题: JobHunting版 - 请教一个DP的问题
即便DP时间上也快不到哪里去。。没啥用。。这种题随便坐就成
A*********r
发帖数: 564
25
来自主题: JobHunting版 - 请教一个DP的题
令F(i,j)表示从范围i..j中取头或尾能得到的最大value,
那么
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 }
第一项是取了i的话,至少能够得到的值(对手可能取剩下的i+1或者j),第二项
是取了j的话,至少能够得到的值。。
下面这个link的第10道题,基本上一样吧。。
http://people.csail.mit.edu/bdean/6.046/dp/

denominations
player
p*******n
发帖数: 4824
26
来自主题: JobHunting版 - DP题目过时了吗?
我觉得是fresh grad倒还好,你们公司的,进去了以后还真有多少人在用DP啊。。。
m***g
发帖数: 90
27
来自主题: JobHunting版 - 问个.ihas1337code blog上面的经典DP题
弱问什么事 dp ...
h*****g
发帖数: 312
28
来自主题: JobHunting版 - google 一道dp 题
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
来自主题: JobHunting版 - 被DP郁闷到了...
再去仔细看例子。DP其实跟贪心一样,是一种思路;不要去背题。
g**********y
发帖数: 14569
30
来自主题: JobHunting版 - 被DP郁闷到了...
要把可以递归的东西拎出来,有时候很困难。你要知道贪心可以解,一般来说离解就不
远了。即使知道DP可以解,甚至看了答案,有时都不是很直观的。
举个topcoder的例子,油漆匠刷条纹,象ABCABCA, 问最少刷几次。我读那code, 关键
的就几行,读了我很久才想明白。
l***i
发帖数: 1309
31
来自主题: JobHunting版 - 被DP郁闷到了...
Even those in top 100 in topcoder cannot work out hard dp problems sometimes
.
k*j
发帖数: 153
32
来自主题: JobHunting版 - DP interview question
网上找来的题目
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
来自主题: JobHunting版 - DP interview question
Don't think this is a DP problem. Look into the optimal substructure
carefully.
l***i
发帖数: 1309
34
来自主题: JobHunting版 - DP interview question
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.
A**u
发帖数: 2458
35
来自主题: JobHunting版 - 练练DP吧,呵呵
你的dp水平真不是盖的
s****a
发帖数: 528
36
来自主题: JobHunting版 - 练练DP吧,呵呵
第二题好像是GREEDY,不用DP
r*******n
发帖数: 266
37
来自主题: JobHunting版 - 关于DP的问题
也不全对....对任何finite coin set...如果钱数足够大, 解一定是greedy的
但是这个门限要用DP来解
p*****2
发帖数: 21240
38
来自主题: JobHunting版 - 关于DP的问题

第一道题,假设coin 是 90, 50, 1
给你100
如果用你的方法就会得到1个90,10个1,一共11个。 如果dp的话就是2个50.
p*****2
发帖数: 21240
39
来自主题: JobHunting版 - 关于DP的问题

第二道题是我看错了,还是你改了。第二题用dp就是为了防止重复计算的。
g*********e
发帖数: 14401
40
来自主题: JobHunting版 - 关于DP的问题

这题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*******1
发帖数: 2454
41
来自主题: JobHunting版 - DP与Greedy的题
弱问,dp咋做的?
b***u
发帖数: 12010
42
来自主题: JobHunting版 - DP与Greedy的题
greedy难在不知道greedy可以。用dp绕半天浪费时间。greedy关键要能证明能贪

in
q***y
发帖数: 236
43
来自主题: JobHunting版 - 问道DP题:平分数组
给一个全正数的数组,大小为N。将其分成连续的K段。要求每段的和尽量平均。也就是
最大化最小段的和。这个DP公式怎么列啊?
p*****2
发帖数: 21240
44
来自主题: JobHunting版 - DP感受 (高手请绕行)

没有呀。我去年连DP都不会,面试全fail掉了。
p*****2
发帖数: 21240
45
来自主题: JobHunting版 - DP感受 (高手请绕行)

没有呀。我去年连DP都不会,面试全fail掉了。
l**b
发帖数: 457
46
来自主题: JobHunting版 - DP感受 (高手请绕行)
CLRS上面是不是有一个专门的recursion+cache的叫法?memoization?那个大牛给定义
一下。DP还是好难想出来啊。
t****a
发帖数: 1212
47
来自主题: JobHunting版 - DP感受 (高手请绕行)
楼上的都是大牛,抛砖引玉,介绍介绍偷懒的办法
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
来自主题: JobHunting版 - DP感受 (高手请绕行)

我觉得说的很准确。跟我理解的一样。没有提到的就是,我觉得DP初始化还是蛮tricky
的。需要点经验。
d**********x
发帖数: 4083
49
来自主题: JobHunting版 - DP感受 (高手请绕行)
poj上遍地都是啊
列状态迁移函数,dp解决问题基本都要属于机械化题目了。。
a********m
发帖数: 15480
50
来自主题: JobHunting版 - DP感受 (高手请绕行)
n维的正常,不一定就难,关键是状态和转移。不过确实一般比较花时间,面试题少见
。需要20多分钟能解决的dp问题应该都比较简单。
首页 上页 1 2 3 4 5 6 7 8 9 10 (共10页)