f*******b
发帖数: 520 | 1 这题是要上DP的，LZ用的方法和我开始一样，但通过不了大数据，不是DP的问题，是所
用算法本身的问题，我改了后就能过大数据了：
public boolean isMatch(String s, String p) {
int count=0;
for(int i=0;i
if(p.charAt(i)!='*') count++;
if(count>s.length()) return false;
if(s.length()==0) return true;
if(p.length()==0) return s.length()==0;
boolean[][] blc=new boolean[s.length()+1][p.length()+1];
blc[0][0]=true;
for(int j=1;j
for(int i=... 阅读全帖 |
|
s********u
发帖数: 1109 | 2 哦我大致明白了，就是通过space cost来换取time cost的，就是dp？
比如这个题：
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
的答案。
如果要求用dp的话，递归还是要比循环好写很多吧。。 |
|
s*****h
发帖数: 155 | 3 你说的cache的这种属于自顶向下的DP，应该算是递归，需要一个global var
CLRS专门有一章讲DP的，有背包，编辑距离以及折棍子几个例子，讲得很清楚 |
|
s******c
发帖数: 1920 | 4 DP 可以用递归来实现 (算出来一个子问题的解以后存下来 下次直接查表).
也可以不用递归直接用查表填表的方式实现.
我上的算法课上, 老师实际上先用递归来演示DP的精髓. |
|
r*******h
发帖数: 315 | 5 最直观的递归往往会重复计算一个子问题，DP主要目的是解决子问题的重复解带来的指
数级开销，但是并不意味着DP不能和递归共存。 |
|
l*n
发帖数: 529 | 6 leetcode的dp已经不少了。再增加，思路总还是一样的，毕竟dp的模式太固定了。 |
|
s********u
发帖数: 1109 | 7 感觉linkedlist用那个dummy node很好用
其实能用dp的题很多吧，只是有的太普通了看上去就只是一般的循环。
最近总结的：
e.g.1 Climbing takes n steps to reach to the top. Each time you can
either climb 1 or 2 or 3 steps. In how many distinct ways can you climb to
the top? ( CtCI 9.1 ,Leetcode: Climbing Stairs）
e.g.2 How many paths are there for the robot to go from (0,0) to (x,y) (
CtCI 9.2, Leetcode: Unique Path)
e.g.3 Write a method to return all subsets of a set. ( CtCI 9.4 )
e.g.4 Write a method to compute all permutations of ... 阅读全帖 |
|
b*******e
发帖数: 123 | 8 My approach is very similar to yours. the difference is the meaning of DP
table. My DP table is 1-D bool, it tracks whether there exist a word break
from i to end. When you do DFS, you can skip the index that doesn't have a
solution when going forward. |
|
b*******e
发帖数: 123 | 9 感觉dp和recursion都是解决recursive equation 的。如果你方便把recursive call
的输入变成有限n-维区间上的整数，就可以建dp table。不方便就用recursion +
memoization。 |
|
p*****2
发帖数: 21240 | 10
key。
昨天发现原来clojure本身就支持memorize呀。这样的话，用clojure做dp不是太爽了，
cache都不用自己搞了。
dfs＋cache dp王道呀。 |
|
|
z****e
发帖数: 54598 | 12 其实dp很容易想啊
找跟之前结果的关联
而且代码实现也简单
比树和链表容易，树状结构改造还有链表的处理很容易写错
小细节比较多
我还更喜欢dp |
|
r******j
发帖数: 92 | 13 关于dp的top down和bottom up。一般我都是先从top down的recursion开始考虑，然后
找出重复计算的地方，如果用memorization的话，直接存一下，以后再查就好了。如果
这样考虑的时候，我们存的一般都是尾巴上的结果，然后一点一点的递归到头，就有结
果了。可是我们bottom up的时候是从头一点一点的到尾巴。感觉这是两种不同的思路
啊。也就是说，是不是所有能用top down解的dp问题都能用bottom up解呢？我发现我
做的题好像都是呢。如果是的话，为什么呢？ |
|
l*******g
发帖数: 82 | 14 dp是啥的缩写？
关于dp的top down和bottom up。一般我都是先从top down的recursion开始考虑，然后
找出重复计算的地方，如果用memorization的话，直接存一........ |
|
s*****i
发帖数: 32 | 15 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
好像别的公司也问到了。
简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
。求问大牛们如何解答？
谢谢！ |
|
M**********s
发帖数: 8 | 16 这是2D bin packing问题吧？这样的话就是NP-hard
先问问是否有额外的条件，照片大小、张数之类的
如果额外条件的话，应该无法在polynomial time求最佳解
可以构思一些一些heuristic approach
题外话，游戏常需要把很多不同大小的textures压在同一张texture
就是要用类似的方法
但optimize的目标不一样：
游戏要用最少的「牆壁」，而这题是只有一面牆壁要贴最多的照片。
不知道我记得的跟您说的是不是同一题
USACO 1.4.1 Packing Rectangles 那道题只有4个矩形，brute force就解掉了
但如果有30张大小不同的照片恰好可以塞在一个大rectangle中，可能是找不出最佳解的
我觉得2D DP不可行，原因如先前有人提到，就是无法model不同大小照片造成的縫隙
另外如果他真的是NP-hard，也显然不可能reduce成2D DP |
|
h*****u
发帖数: 109 | 17 有道理。除了guillotine cut，Gilmore and Gomory 还允许 multiple items，但是这
个题目只是允许最多一个。
这个也不属于multi-dimensional knapsack, 因为不是简单的相加关系。
我找到最相关的是：An exact algorithm for general, orthogonal, two-
dimensional knapsack problems, European Journal of Operational Research 83 (
1995) 39-56。但是也不是DP.
感觉如果要表征solution，需要把已经剩余区域的所有极点(extreme points)都记录下
来。如此，怎么设计DP?
o |
|
g*****g
发帖数: 212 | 18 ---------
--|
|
------|
假设每种尺寸无限：
减下去右 {（x1,y1）,(x2,y2)}，有两种分割：
1） {(0，0),(x2,y1)} {(0,y1),(x1,y2)}
2) {(0,0),(x1,y2)} {(x1,0),(x2,y1)}
是否可以如此
DP是求 max( 1),2) ) +1
DP 基本元素是 矩形（长和宽），所以可以用一个matrix(n X m)表示。 |
|
m********7
发帖数: 1368 | 19 大家新年好~！
leetcode上 stock III的这个 dp 解法，http://www.cnblogs.com/caijinlong/archive/2013/05/01/3053165.html
上讲的dp算法看懂了，但是代码实现和算法如何对应起来的，没看懂。。
欢迎大牛们指导~~谢！！
code:
int maxProfit(vector &prices) {
int f[3] = {0};
int g[3] = {0};
int n = prices.size() - 1;
for (int i = 0; i < n; ++i) {
int diff = prices[i+1] - prices[i];
int m = min(i+1, 2);
for (int j = m; j >= 1; --j) {
f[j] =... 阅读全帖 |
|
l**********g
发帖数: 16 | 20 请教一道DP问题，大概是这样的：
有一个长为L的木料需要割开，切的位置在一个数组里A[0...N]，从一个地方切开的
cost是当前所切木料的长度。按不同的顺序切割，得到的total cost是不一样的，问怎
么切cost最
小。
我对题意的理解是，比如一个木料现在10米长，然后切的位置是2米处，4米处和7米处
（就是说arr A里A[0]是2，A[1]是4， A[2]是7）。那么比如先切2米，那么得到cost是
10（因为现在木料长度为10），然后切4米处，那么cost变成10 + 8(因为8是现在切的
时候木料的长度)。然后切7米处，cost变成10 + 8 + 6。那么这种切法总共的cost是24。
这题DP应该怎么写？递推关系是什么？谢谢！ |
|
A*****i
发帖数: 3587 | 21 这题stack这个就很好啊，便于理解
如果非为了DP去想DP就没意思了
其实公司里写代码就是图个省事，高深晦涩的代码只能让同事骂娘 |
|
r****m
发帖数: 70 | 22 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
r****m
发帖数: 70 | 23 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
a***e
发帖数: 413 | 24 Given n pairs of parentheses, write a function to generate all combinations
of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Recursive 的写出来了，但DP的不知道怎么做，看了别人的code也不太懂，尤其是
for(int l=0;l
buff[i].push_back(buff[j][k]+"("+buff[i-j-1][l]+")");
在做啥，为啥idx要i-j-1 等完全不清楚。
另外，大家有推荐学习DP的方法么？多谢
class Solution {
public:
vector generateParenthesis(int n) {
vecto... 阅读全帖 |
|
C********e
发帖数: 492 | 25 你贴的这个解法不是DP
而且我不认为此题可以用DP做。。。
combinations |
|
a***e
发帖数: 413 | 26 Given a string s, partition s such that every substring of the partition is
a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced
using 1 cut.
我刚开始看DP，大概有点idea，但怎么都做不对。有同学知道下面这个double loop 到
底怎么错了吗？有什么好的学习DP的方法分享吗？多谢！
class Solution {
public:
int minCut(string s) {
int n=s.size();
if (n<=1) return 0;
vector> b(n, vector<... 阅读全帖 |
|
b******d
发帖数: 794 | 27 当然是dp, guaranteed O(n*m) time, O(n) space
memorization search worst case还是exponential的复杂度，O(m*n) space, 只是找
不到dp算法时没办法才用。 |
|
发帖数: 1 | 28
为什么要用DP？因为leetcode上DistinctSubsequences这题我只会DP解法，没想到其他
方法。
准确的说space/time应该是O(n*m) n是s1的长度，m是s2的长度。
你的解法似乎有问题，比如s1是aabbb, s2是abb (不考虑楼主的题，只考虑leetcode上
DistinctSubsequences)，结果应该是6。 |
|
p**r
发帖数: 5853 | 29 你说的没错，我的DP解法有问题，
如果用DP解，应该是每个字符符合情况都基于前一个字符的情况做叠加。 |
|
发帖数: 1 | 30
不明白；len2肯定是偶数， java里 len2/2+1和(len2+1)/2+1等于相同的整数，没有
区别啊；
另外把所有所有len2 / 2 + 1改成(len2+1)/2+1， 这里报了错index out of range
error
.....
for (int j = 0; j < len2 / 2; j++){
dp[i + 1][j + 1] = dp[i][j + 1];
..... |
|
l****u
发帖数: 1764 | 31 貌似不是greedy，也没太好的办法dp，除了brute force，真没想到什么好的dp方法呢
，sub problem貌似非常多啊。。 |
|
H**********5
发帖数: 2012 | 32 我的感觉是:把测试流程全部手动运行一边，写在笔记本上。写过一边后印象就深多了
。我目前刚把lc的一维dp测试流程跑完，开跑二维dp，当然这个方法不一定适合lz |
|
s****a
发帖数: 794 | 33 fb只鼓励问中等难度的题 不鼓励问dp 但是也有人问DP
我遇到的中国人大多都是挂design和behavior 挂算法的少 |
|
s**********g
发帖数: 14942 | 34 考dp的不少
我电面都遇到dp呢
toplogical sort当然要看
我面俩公司都遇到了。。。 |
|
r*****s
发帖数: 1815 | 35 拓扑排序本来就是本科生知识
现在转行的太多。。。。拓扑排序也变成高级知识了。。。
: 考dp的不少
: 我电面都遇到dp呢
: toplogical sort当然要看
: 我面俩公司都遇到了。。。
|
|
h***e
发帖数: 866 | 36 DP还没存够，rate就又涨了，唉。。。老老实实租房，把DP投资祖国房地产，呵呵 |
|
s******k
发帖数: 6659 | 37 今天Discover的邮件着实是个blow-out。在这儿想建立一个DP帖，汇总一下已知的信息
，所以就不要灌水了。
已有的DP来自FlyerTalk，大约是16-18号的purchase都给了『one-time courtesy』。
23号以后的基本都悲剧了。这中间的几天基本是mixed。
基本结论是Discover把所以大额默认成GC，然后要求用户提供receipt来证明不是（
which is ridiculous)
为了能更好的确认一下到底这个线在哪里，现在主要想统计一下500刀以下的Apple
Pay，哪些收到了邮件，哪些没收到。500刀的VGC就不要po了，500以下的各种GC或者
不是GC都可以。格式如下 （以Walgreens为例）：
--------------------
日期：9月20日
商家：Walgreens
买的东西：饲料
总金额：250
是否收到邮件：否
--------------------
没收到邮件的话基本可以确认默认过关（毕竟Discover没有level 3信息，不可能知道
你买了啥）。
当然Discover最近的公关得有的忙了。虽然最后有可能... 阅读全帖 |
|
n******7
发帖数: 839 | 38 我有两张，一张plus大概1、2月份的时候打去要，什么也没要到。另外一张premier，
今天刚刚打去要，还是什么都没有。我记得大概一两年前看到网上DP是southwest的卡
一直很容易要到大概6K点左右的retention的啊。现在怎么完全没有了？奇怪的是，反
而是蓝宝石要到retention的dp越来越多了，以前蓝宝石是完全没有retention的。 |
|
f******9
发帖数: 23 | 39 貢獻一下DP 想嚕Amex 300 - 50 offer 用MPX買Amazon GC
雖然類別是Air travel 不過大概透過MPX不算直接跟航空公司買吧
刷了三百(posted)但是沒有看到 credit 入賬, 大概是沒希望了
之前嚕boxed or 其他offer 幾乎都是立刻看到credit..
直接買航空公司的GC會不會算 求個DP |
|
|
D***s
发帖数: 5613 | 41 就是报告个dp，犯得着看不起么？
一年过彩虹桥的车有上百万，有点dp还是会对群体有帮助的 |
|
t********n
发帖数: 996 | 42 是18年报销的dp吗？我17年底买的SW也报了，但是看18年的dp好多都没报就一直没敢买 |
|
t******i
发帖数: 92 | 43 刚找到工作，月薪2500以上。雇主提出帮着申请letter of consent。查了一下，DP申
请LOC方便快捷。不好的地方就是如果老公丢工作，我也不能工作了。从这个角度出发
，好像应该申请EP,就是不知道EP申请容易不容易？另外，在交税福利等方面，拿EP工
作的人和拿LOC工作的DP有什么差别？ |
|
m********f
发帖数: 5 | 44 我是ep，准备给老婆申请dp，mom网站说需要材料是护照，结婚证公证，dp表，请问还
需要其他的
吗，比如学历公证，出生证明什么的？还没来得及问系秘，有知道的在这里先给我说一
下，好早
做准备。谢谢。 |
|
w******i
发帖数: 429 | 45 刚到这个版来看，看了一个mm展示了一些DP买的裙子~心痒，手痒~
看上了两件，求建议
不知道他们的s码的大小是如何的？size chart上描述的，我觉得s和2号应该差不多的
。但是没买过，实际上我连DP都没听过哈~买过的jms有建议么？
另外他们家免邮费return么？如果是，那么就试试啦~~bow~半夜买裙裙真是开心啊~
--不好意思，之前的ms照片的url贴的不对，然后删除了又发了一次~：（ |
|
T***a
发帖数: 182 | 46 DP用来review的NEX工程机难道不是sony给的？
你是说sony这次乌龙了？拿了个半成品给DP? |
|
|
h*******g
发帖数: 10585 | 48 不是x3的功劳咩？
我朋友在越南拍的也很毒，可惜我没存档
我有些玩摄影的朋友，数码都是dp =。=
我觉得这个做的好点，就像胶片时代的P&S了
dp-2x可以堪比T2 |
|
r**********1
发帖数: 1004 | 49 搞个一百多的 DP-1x, DP-2玩玩就行了 |
|
