Archive for July 19th, 2013
这个好做，是build up的一维DP。还是，把状态d一定义，关系就自然出来了。d[i]表示能不能跳到i处，要是能跳，则再把从i处能跳到的别的地方全set up了。这样过一遍数组，就出来了。
public boolean canJump(int[] A) {
boolean d[] = new boolean[A.length];
d[0] = true;
for (int i = 0; i < A.length; i++) {
if (d[i] == true) {
for (int j = 1; j <= A[i]; j++) {
if (i + j < A.length)
d[i + j] = true;
}
}
}
return d[A.length - 1];
}
然后大的就挂了有木有！！卧槽dp原来也不一定是最优解啊！！你的dp是个两层循环，有很多重复（比如到j，从i已经跳到它过了，但是i+1也能跳到它，所以重设了一遍true）。没必要把每个i能不能走到都算出来，只要算出最后一跳能不能>=n就行了。
算法：keep一个var，表示目前看来最远能走到哪。比如现在在i上，已知之前算的从0~i-1上最远就能跳到m处，那么如果i <= m，就说明i这个位置是能跳到的。为什么这就说明了呢？因为你的m是在0~i-1中的某个index上算出的，比如i0，那么说明从i0一直到m全能跳到（一步一步跳），而i还>i0，所以i到m之间当然也能一步一步跳到了。
public boolean canJump(int[] A) {
int farIndex = 0;
for (int i = 0; i < A.length; i++) {
if (i <= farIndex){
farIndex = Math.max(farIndex, A[i] + i);
}
}
return farIndex >= A.length - 1;
}
卧槽这道还真自己做出来了。感觉是二维DP，尽管没让求什么最大最小个数之类的，只是boolean，但是递推关系还是有的。其实只要把状态敢于定义出来（旁边标注物理意义），状态转移方程就能写出来了。然后就是处理最开始。思路：
- 一开始是这么定义的：d[i][j]: whether s1[0, i]的substring和s2[0, j]的substring能够cross match s3[0, i + j + 1]这个substring。比如ab和c，即(0, 1), (0, 0)，能否合起来是acb(0, 2)。要点是s3的index要+1，这个一开始就想错了直接i + j的。
- d[i][j] = s3[i + j + 1] == s2[j] && d[i][j – 1] == true （用第s2的j个来填s3的i + j + 1个能成功）， OR s3[i + j + 1] == s1[i] && d[i – 1][j] == true （用第s1的i个来填s3的i + j + 1个能成功）
- d[i][j]物理意义一定要搞清楚，因为d[0][0]说明拿了两个元素，那么它对应的是长度为2的s3，这index干脆就乱套了。这个时候，换一种方式定义：d[0][0]表示从s1中拿0个，s2中拿0个，然后组成s3（长度为0 + 0)能不能成。这个肯定是true。d[1][0]就能表达只从s1中拿一个，s2中不拿，然后组成长度为1的s3这种make sense的意义了。这样i, j就要一直到=size这么大。所以之前的i + j + 1改成i + j – 1，才能真的往string里charAt。
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length())
return false;
boolean[][] d = new boolean[s1.length() + 1][s2.length() + 1];
d[0][0] = true;
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (j > 0 && s3.charAt(i + j - 1) == s2.charAt(j - 1) && d[i][j - 1])
d[i][j] = true;
else if (i > 0 && s3.charAt(i + j - 1) == s1.charAt(i - 1) && d[i - 1][j])
d[i][j] = true;
}
}
return d[s1.length()][s2.length()];
}
Lexi's Leetcode solutions 