45.Jump Game II

解题思路

性质：
如果i是从i-1跳一步到达的，那i位置的最少跳数是<i> = <i-1>+1;
如果i是从i-2或是之前跳到的，则有<i> = <i-1>
即有<i> >= <i-1>.
利用贪心算法，每次求取当前阶段的最优解，最终得到最后的结果。
目标函数：max(cur,i+A[i])//求局部最优解

方案一

时间复杂度：O(n)
空间复杂度：O(1)

public int jump(int[] nums) {
		int ret = 0;// 当前跳数
		int last = 0; // 上一跳可达最远距离 :ret
		int cur = 0;// 当前一跳可达最远距离 :ret + 1
		for (int i = 0; i < nums.length; i++) {
			// 需要进行下次跳，需要更新last和当前执行的跳数
            // i 不仅是数组下标， 还是已经到达的距离
			if (i > last) {
				last = cur;
				++ret;
			}
			// 记录当前可达的最远点，保证每次以尽可能大的步伐往后跳
			cur = Math.max(cur, nums[i] + i);
		}
		return ret;
	}

方案二

把问题转换成BFS问题。
第i层节点是指那些可以通过i-1步跳跃到达的节点。
例如：2 3 1 1 4， 可以看成 2  ||  3 1  ||  1 4

public int jump1(int[] nums) {
		int n = nums.length;
		if (n < 2)
			return 0;
		int level = 0, currentMax = 0, i = 0, nextMax = 0;

		// 当前层的节点数目>0
		while (currentMax - i + 1 > 0) { 
			level++;
			// 遍历当前层，求局部最优解
			for (; i <= currentMax; i++) { 										
				nextMax = Math.max(nextMax, nums[i] + i);、
				//如果最后一个元素在level+1层，则最小的跳跃数就是level
				if (nextMax >= n - 1)
					return level;  									
			}
			currentMax = nextMax;
		}
		return 0;
	}