Posts Tagged ‘greedy’
[leetcode] Jump Game 2
Posted on: July 21, 2013
这个是要算到达最后一步最少要跳几步。不用非的跳到last index上，越过去也算。
还是，用dp的话有重复，不需要算d[i]跳到每一步用的最小步数，只要算最后一步能不能跳到，最少用几步就行了。这题其实自己还不够理解，下次还得重做。
算法：在每一步i，都已知到当前这一点用的最小step数k（但是不是存在数组里的，而是local variable）。在每层小循环里，都是“走一步能到的这些点中”， 最远能到哪一点，记载为p，那么到p就能最少用k + 1步就能到了。如果p出了数组边界，直接返回k + 1，就做出来了。要是没出界，则小循环之后，继续下一层循环，但是下一层循环和当前循环不重合，因为下一层说明多走了一步，则k++， 那循环的起始部分就是上一个小循环的尾。（每层小循环的意义是：用k步能走到的这些点，都试探一下，看看从他们身上走一步最远能走到哪）。
public int jump(int[] A) {
if (A.length == 0 || A.length == 1)
return 0;
int examingStart = 0;
int currSectionCanReach = 0;
int steps = 0;
while (examingStart <= currSectionCanReach) {
int examingEnd = currSectionCanReach;
int nextSectionCanReach = examingStart;
for (int i = examingStart; i <= examingEnd; i++) {
nextSectionCanReach = Math.max(nextSectionCanReach, i + A[i]);
if (nextSectionCanReach >= A.length - 1)
return steps + 1;
}
examingStart = examingEnd + 1;
currSectionCanReach = nextSectionCanReach;
steps++;
}
return -1;
}
这个好做，是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;
}
Lexi's Leetcode solutions 