存档

2012年9月 的存档

百度面试题:POJ 2192 - Zipper

2012年9月30日 8 条评论

---

百度二面的时候有一道题目没有答上来,回来一查,原来是POJ上的原题,是一个DP问题,当时有向这方面想,但始终没有找出重叠子问题,网上看到别人定义的子问题,感觉真心简单,关键看是否能找出子问题了,这个积累不是一时半日的,自己还是太菜。刚刚到POJ上AC了这道题,附题目链接:

POJ 2192: http://poj.org/problem?id=2192

题意:就是给定三个字符串A,B,C;判断C能否由AB中的字符组成,同时这个组合后的字符顺序必须是A,B中原来的顺序,不能逆序;例如:A:mnl,B:xyz;如果C为mnxylz,就符合题意;如果C为mxnzly,就不符合题意,原因是z与y顺序不是B中顺序。

DP求解:定义dp[i][j]表示A中前i个字符与B中前j个字符是否能组成C中的前 (i+j) 个字符,如果能标记true,如果不能标记false;

有了这个定义,我们就可以找出状态转移方程了,初始状态dp[0][0] = 1:

dp[i][j] = 1 如果 dp[i-1][j] == 1 && C[i+j-1] == A[i-1]
dp[i][j] = 1 如果 dp[i][j-1] == 1 && C[i+j-1] == B[j-1]

代码如下:

阅读全文...