[Leetcode] 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.)

 

个人觉得是贪心及动态规划, 转来的

	/*
	 * We use "last" to keep track of the maximum distance that has been reached by using the minimum steps "count", whereas "current" is the maximum distance that can be reached by using "count+1"
	 * steps. Thus, current = max(i+A[i]) where 0 <= i <= last.
	 */
	public static int jump(int[] A) {
		int step = 0; // 当前跳数
		int last = 0; // 上一跳最远距离，从A[0]进行count次jump之后达到的最大范围
		int currentMax = 0; // 当前一跳可达最远距离，从0~i这i+1个A元素中能达到的最大范围

		for (int i = 0; i < A.length; i++) {

			// 说明count次jump已经不足以覆盖当前第i个元素，需要进行下次跳跃，则更新last和当执行的跳数count
			if (i > last) {
				step++;
				last = currentMax;
			}

			// 记录当前可达最远
			currentMax = Math.max(currentMax, i + A[i]);
		}

		// 永远到达不了
		if (last < A.length - 1) {
			return -1;
		}
		return step;
	}