[leetcode]JumpGameII

新博文：[leetcode]Jump Game II

 http://oj.leetcode.com/problems/jump-game-ii/

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

 

看题中的意思貌似是不会出现0元素，因此总是可以走到头的，就暂不考虑这样的边界了。拿到这倒题的第一思路是从后往前DP，我们用step[i]表示第i个元素到终点的最小跳数，则

step[ i ] = 0;(i == A.length - 1)

step[ i ] = min{ step[ j ] : i <  j <= min(i+ A[ j ],A.length -1) } + 1

因此不难写出这样的代码

 public int jump(int[] A) {
		int length = A.length;
		int[] step = new int[length];
		step[length - 1] = 0;
		for(int i = length - 2; i >= 0 ; i--){
			int min = Integer.MAX_VALUE;
			for(int j = i + 1; j < length && j <= i + A[i]; j++){
				if(step[j] < min){
					min = step[j];
				}
			}
			step[i] = min + 1;
		}
		return step[0];
	}

时间复杂度自然是O(N*N) 面对这样的case：

[25000,24999,24998,24997,24996,24995....5,4,3,2,1]对每一个元素都要重复计算前面的所有元素，超时是自然的。

花费了一个半小时才AC，囧！由于本题并没有要求我们计算出跳跃路径，因此我们可以单纯的求跳数， 采取贪心的算法，比如2,3,4,1,0,5对于2，其覆盖范围是3,4,，因此我们只需要求3,4，的最大覆盖范围即可，既然在4的覆盖范围中求下一跳的最大覆盖范围。每一次更新覆盖范围，就说明要进行一跳。代码如下：

public int jump(int[] A) {
		int step = 0;
		int cover = A[0];
		for (int i = 1; i < A.length; ) {
			int max = cover;
			while (i <= cover && i < A.length) {
				if (A[i] + i > max) {
					max = A[i] + i;
				}
				i++;
			}
			cover = max;
			step++;
		}
		return step;
	}

 我去。。看了别人的算法，竟然发现惊人的相似o(╯□╰)o。。。。。