P****d
发帖数: 137 | 1 在国内一个大学的网站上找到原题了，GOOGLE问过
http://soj.me/1767
这个如果确定一条最佳路径再找第二大的肯定不是最优化的，然后有朋友说要用四维DP
，不过还是不知道怎么个DP法，DP关系是什么
求大牛指教，谢啦 |
|
|
p**r
发帖数: 5853 | 3 看过三分地的原题，没要求用DP，
如果用DP，感觉是大概这样思路：
先最简化问题：s1忽视所有invalid字符(扫描O(n)的时候直接忽略了)
s2=ab
1: ab=1
2: aab=a(ab)=ab+ab=2
3: abb=(ab)b=ab+ab=2
//2,3为同一个f
4: aabb=(a)ab(b)=aab+abb=4
然后再分析abc的情况
这里a可以是aa，aaa，aaaa
感觉这题用DP很累，分析半天，还是用我的吧，哈哈。
programming |
|
z*********n
发帖数: 1451 | 4 我面试从来没遇到过dp。其实面试题里面的dp题都是简单题，毕竟是有模板可以套的题
型。
当然dp想出难可以出的很难。 |
|
H**********5
发帖数: 2012 | 5 我上次onsite连续遇到4到dp，还是那种中等难度的2维 string dp，虽然是原题但没准
备到秒跪
: LZ是experienced的对吧。感觉DP在刷题圈炒的很凶但几乎没见几个公司真考的。
: 除了BFS DFS，感觉真正最常考还最容易错的是binary search及各种变种以及
string相
: 关的题目（各种奇葩操作，还有一票trie上的）。建议LZ把这类题刷一遍。
|
|
|
b******1
发帖数: 255 | 7 老公如果去新加坡做博后，月薪要是不上5000可以给老婆申请DP吗？如果老婆在新加坡
生孩子，是不是必须老婆也有wp才可以给孩子申请DP，否则如果老婆没工作孩子就申请
不了DP了吧？ |
|
j********l
发帖数: 551 | 8 【 以下文字转载自 SpeedSkating 俱乐部 】
发信人: junglebell (Jungle Bell), 信区: SpeedSkating
标 题: 给讲讲怎么练DP吧
发信站: BBS 未名空间站 (Tue Jan 12 11:56:29 2010, 美东)
据说新手不适合上来就练DP。但是还是心里痒痒。在youtube上头看Roger Schneider的
monster DP还是很羡慕的。Eddy Matzger有个很好的video讲一些drill。但是那些
drill练起来还是不太容易。不知道练过的大侠们是不是这么练的？另外我这半马一小
时的水平，是不是还是老老实实从classic stroke练起？ |
|
|
z*****i
发帖数: 941 | 10 当王徽在小说最后问出“So, how about love?”的时候，他正巧完成了DrunkPiano交
付给男主角的艰巨任务，也震惊了一下毛主席，那就是竟然有人把对自己的误解提
升到了一个信念的高度，永恒的长度。
这个误解的媒介是网路，更确切来说是未名交友，但媒介永远只是作者传达感受的
工具，而不是讨论或打击的真正对象。男女主角这个误解的本质来自于新一代留学
生感情生活的苦闷。有些人幸运地在苦闷来临之前有了归宿，有些人运气不错的找
到伴侣逃过或解决了这场苦闷，有些人在苦闷里挣扎守护着遥远的理想，这些姑且
称之为第一类人，DP暂时不管。另有些人在跟现实的对峙中节节败退，手中虽然摇
的仍是一颗红心的大旗，心中却不知不觉竖起了多手准备，机关算尽的白旗，这是
第二类人--DP在小说中描绘的对象，而且把他们写到绝，写到极端，写到典型不在
夙昔，而是今夕。
DP到底是怀着讥讽还是同情的角度出发其实不太重要，她关心的是这红白两旗之间
的距离，以及人如何在特定情境下合理化这冰与火的冲突。唐王两人粉墨登场，演
绎了一套套拜金(或皮相美)与拜心灵的辨证逻辑，化矛盾为统一，统一中又演化矛
盾，内心戏可谓眼 |
|
s******s
发帖数: 13035 | 11 dp当然对dp, dvi肯定不行，hdmi也不一定能上2560.
你显示器只有这两个port？ |
|
g*******t
发帖数: 7704 | 12 Dvi方便点，好多显示器没有hdmi，有mini dp， 电脑上是micro dp，这帮厂商就是折
腾用户， |
|
c******n
发帖数: 16666 | 13 dp转dvi amazon 10块不到有个转接头
我们公司一堆dell的都是dp的 其实实际使用中很少有上超高分辨率的 恼火得很 |
|
k********s
发帖数: 5024 | 14 哦哦，明白了
珍爱生命，远离DP，也不想和DP玩下去了 |
|
s*****f
发帖数: 160 | 15 老大，DP卡没有记录卡号的receipt也安全，因为面额小，大部分都是25的，这些肉鸡
看不上的。
DP卡如果合并成大额GC，一定会有receipt, 上面记录着合并前的来源，是不是从25一
张的合并来的。
怕就怕大额没收据的，要是store credit 没收据更可怕，没有收据你根本不知道是怎
么来的。您交易上千次没出过事那是幸运，最近事情可是不少。 |
|
T*********e
发帖数: 39815 | 16 在DP下单尽量用CITI和AMEX的信用卡, REFUND出了问题DISPUTE胜算大一些.
一定避免使用CHASE和HOUSEHOLD/HSBC的卡,不要贪图那点CASH BACK的小便宜
最重要的是,尽量不要违反DP的TERM, 如果自己想冒险,那么先想好能否承担损失,如何
善后.
即便我们目前还能DISPUTE CITI和AMEX,但是不要把这个当成法宝, DISPUTE多了,最后
也就不灵了,不要故意ABUSE 信用卡的DISPUTE |
|
c***u
发帖数: 190 | 17 兄弟，怎么会看不懂？
我用citi 加入membership， 每个月从citi 扣月费。买卡是用chase，总共花了$1750
， 但是refund $350 是到了reissured citi的新卡。很奇怪，噢？ 所以我认为DP是良
心大发，急着要求DP 从新activate我的programs。现在知道内情了，估计activate 也
没戏了。
我发这个帖子只是想大家知道一点我的case，也许会对一些人有点帮助。 |
|
a********r
发帖数: 810 | 18 跟DP打交道不多,两年以前跟风加过一次TE,买了一些gas card，但DP马上说那个link
无效，但是gas card的reward好像还是拿到了。
今年五月底的时候加了AHR+，成功拿到了OYO,也拿到了$25的home depot gift card.主
要是买home depot自己用。买一点好交易的circuit city和JCpenney,有时候自己用，
用不了就二手版卖掉了。我比较懒，只交易email code。huhu.
另外saving smart是附属品，当时就给cancel了。
昨天用了mect的那些link,
加了PTF+,TE+,SE+,还有一个simply you.所有的都拿到了OYO,但是年费都是29.95.不过
除了simply you,free gift card都是$50，所以还是有的赚。simply you也加了oyo,可
能没什么必要。但是习惯养成了，只要offer OYO就从了。还有,如果申请那些plus的时
候拒绝了simply you，登陆plus的时候还是会出来，而且是$25的circuit city
instead of LNT.
P |
|
d*******n
发帖数: 3851 | 19 Use my ld name, new credit card number, and a new address.
I think the reason is I used my ld name enroled dp at a difference address
although I canceled those programs some month ago!
wow, dp is so smart now! |
|
b***l
发帖数: 196 | 20 ☆─────────────────────────────────────☆
bananan (黑白双键) 于 (Fri Dec 7 22:18:31 2007) 提到:
简单,agent也nice
investigation都省了直接charge back dp
☆─────────────────────────────────────☆
sleeping (此ID重新启动) 于 (Fri Dec 7 22:22:15 2007) 提到:
我也是一个星期内结果就出来了。
简单,agent也nice
investigation都省了直接charge back dp
☆─────────────────────────────────────☆
phstar (星星) 于 (Sat Dec 8 10:55:40 2007) 提到:
你们用的是AMEX的哪种卡？
☆─────────────────────────────────────☆
ripplelet (MagicBB) 于 (Sat Dec 8 13:41:11 2007) |
|
m*********e
发帖数: 1139 | 21 买了东西，点了business max,加了14.95的rewards,点了yes后并没出现如何DP的
program啊，不知怎么回事。mmd,白买那个东西了，要了偶6刀的运费！
哪位这两天操作过是可以的吗？具体步骤如何？怀疑偶步骤有误啊，到底点哪个就能出
现DP? |
|
b********e
发帖数: 1946 | 22 现在的地址比较长,加了DP的program以后,在membership 的 profile 里发现地址没有
显示完全. 给DP打电话让他们更正,结果被告知他们系统里我的地址是完全的,而且说如
果我order卡是没有问题的,地址是完全的. 但是还是担心呀,怕地址不完全送不到手里.
大家遇到过这种情况吗? 谢谢 |
|
b******n
发帖数: 2114 | 23 新手，刚加了DP的membership，年费19.95$,但是为什么只看到5%discount的gift card
卖，请问所谓的program如何加入啊。
是必须成为DP的member后才能加入各种program,还是可以直接加入各种program，浏览
了一下精华区，没有找到答案，请各位不吝指教。 |
|
b*********o
发帖数: 1045 | 24 我有两个DP program，以往都是每月3、4号才charge月费，现在不知道怎么改成1号
charge了，9月份的今天(8月31)已经在信用卡上看到pending了，如果我9月1号cancel
，DP会不会退9月份的月费？ |
|
|
f****2
发帖数: 315 | 26 6月1号order了2单, pdf+和she+, 6月2日被dp cancel, 6月5日拒收了包裹.
今天打电话给citi要dispute, 又和dp的csr吵了一架, 然后citi勉强file了
一个dispute, 但是说我很有可能lose.
请问版上的大牛都是如何dispute的? |
|
M*****i
发帖数: 1242 | 27 先帮女友加了dp，用自己电脑。刚申到citi信用卡，所以现在要用自己地址加dp，还用
自己的电脑会不会有问题？
谢谢大家！ |
|
b******e
发帖数: 3348 | 28 我用一张信用卡billing地址不是现在的住址，结果刚刚dp打电话过来问，没接到，dp
就留言教我打一个电话，不敢打，怕cancel membership.....
大家一般都是怎么处理的呢？ |
|
k*******0
发帖数: 12 | 29 快被dp烦死了
10月中旬的时候
我9月的order迟迟未到
10/17 or 10/18打电话去argue
他说会寄affidavit给我填
填好寄回去之后再补发卡给我
但需要notary public…很麻烦
后来检查我的email
有order confirmation
却没有shipping confirmation
结果10/19寄给我9月订单的shipping confirmation
然后卡10/21就到了
代表他们是有办法迅速寄出卡片的…
要寄给我的affidavit也无疾而终
这倒没关系 反正我终究是收到9月的卡了
我在10/19又订了另一笔order
10/20就有shipping confirmation
想说有shipping confirmation就不必太担心寄不到的问题
没想到…
到了11/17还没到
只在11/10寄给我两份affidavit (但我有加了AHR+，PTF+跟SE+)
还缺AHR+的
打电话去跟DP吵了一个小时
跟两个supervisor讲过
即使我已经表达过我的不满
都还是叫我填affidavit寄回去
现在我有两个options
( |
|
d*******n
发帖数: 3851 | 30 俺用chase的visa新卡怎么也入不进去，不知道是chase卡的问题，还是visa卡的问题啊？
换了citi的master卡，立马就成功了，不过citi的master卡2，3年前在dp买过卡，3天
后，dp program竟然全被cancel了，杯具啊杯具！！！ |
|
s********o
发帖数: 52 | 31 谢谢！请收包子.
我只希望加有尽多TOYSRUS和SEARS的,不想加太多其他的搞太复杂.以前只对DP熟悉,
现在还有DP的吗 |
|
w********d
发帖数: 76 | 32 有贴说DP的program都是15的月费。多的每次也就买5张GC，省25total。 除去月费才省
10刀。如果9折卖都要亏本。怎么还有这么多人用DP呢？真的很疑惑，请各位大虾指点
。 |
|
c*********5
发帖数: 5813 | 33 dp CSR的话没一个靠铺的，就我这几年跟dp打交道的经验来看
in |
|
r****o
发帖数: 1950 | 34 DP问题可以用来解决背包问题，硬币问题这种题目。
但通常都只能返回一个最优的sum数，如果想打印出哪些物品或硬币构成这个最优解，
就得要用二维数组或多维数组来存储那些sub-problem的解。这样的话，DP的空间复杂
度岂不是很高。不知道还有没有其他办法可以打印出构成最优解的物品或硬币。请大侠
指教。 |
|
m*****g
发帖数: 226 | 35 貌似经典的DP
given an array of ints, find the contiguous sequence with maximum sum.
我是把每个可能的组合都试的，做出来(n2)的时间
请问DP得怎么做 |
|
l******c
发帖数: 2555 | 36 Why only DP, no LP?
DP is more immportant than LP? |
|
t******h
发帖数: 120 | 37 Write a function that takes in an array of integers and outputs the number
of ways you can combine those integers to obtain a sum of 15.
Example: for [10,5,3,2], output = 2.
我只想到用递归 生成所有结果
如果等于15就把计数器加一
careercup上说可以用DP来做 但是我想不到
请问这个问题用DP怎么做？ |
|
c******n
发帖数: 4965 | 38 recursion ---> memoization ---> DP
is rather simple, it's almost a mechanical translation process
your recursion version for this problem is:
let a[] be the array of possible integers
number_of_ways(N, a[]) = sum( number_of_ways(N- a[i], a[] - a[i]) )
while base case is number_of_ways(0, anything) = 1
and number_of_ways(n , anything) = 0 where n < 0
这个题如果像上面限制每个integer 只能用一次， 用DP 不太好表达 ， 如果可以重复
使用，就很
简单：
for n = 1 to 15:
for (i=1 to MAX_NUMBER_OF_AVAILABLE_INTEGERS ) :
if ( n - a[i] > ... 阅读全帖 |
|
t****a
发帖数: 1212 | 39 Well it is pretty good idea for the binary search here.
DP. |
|
h**k
发帖数: 3368 | 40 赞一个。最后使用的二分查找实在是太巧妙了。
另外，N是为了直接用二分查找来做这题的。
DP. |
|
A*********r
发帖数: 564 | 41 你的意思是直接用2分查找作，而不用DP？
能简单说一下思路吗？ |
|
|
A*********r
发帖数: 564 | 43 (根据建议，修改非DP版本如下）
min=0;
max=N;
while(min
{
x=(min+max)/2;
count=1;
prev=a[0];
for(i=1;i
{
if(a[i]-prev>=x)
count++；
if(count>=k) break;
}
if(count
else min=x;
} |
|
h**k
发帖数: 3368 | 44 han6就是实现的你改进的DP算法的最后的那个二分查找。他是想说明这里用线性查找和
二分查找效率差不多。
集，所以会是O(M*LogN)。。你的2分，是在M个元素中二分，找出一个最小的合适元素
curr，使得最后K元素子集的半径为X,所以复杂度是O(K*logM).
一次）， 所以总复杂度等于sort的复杂度+O(k*logM*logN). |
|
|
m**q
发帖数: 189 | 46 刚看过了CLRS的章节，举得例子倒是清楚，后面的思考题
看了一遍全都不会啊... 板上好多dp题也没思路。这要是
去interview遇到dp肯定挂了啊..
大家有什么建议么？请教... |
|
m********l
发帖数: 4394 | 47 基本上DP就是Brute Force的一种
不过可以用DP的问题要重算很多东西
为了节省资源， 把要重算的东西存起来 |
|
j*******r
发帖数: 52 | 48 agree，我现在看到感觉要DP的题目都是先想brute force，然后想一下是否可以存储重
复的中间结果，把brute force转成dp。。 |
|
|
e***s
发帖数: 799 | 50 如题，
DP： time O(n*m) space O(n*m）
BF: time O(n*m) space O(1)
为什么我看那本屌书说DP更好，还没说理由。是不是我傻B了，求拍～ |
|
