45. 跳跃游戏

问题45 跳跃游戏 ★☆☆☆☆

https://leetcode-cn.com/problems/jump-game-ii/

贪婪算法的思路我是参考了官方题解的，但是坦白讲，官方题解的描述和代码我觉得都不大好理解。我尝试用自己的理解表达一下：贪婪算法嘛，简单说就是每一步都争取最好的那个选择。比方说现在位于nums[0]，那么这第一跳能到达的最远节点的下标是0+nums[0]，记为i。那么问题来了，在[1..i]这些元素中，跳到哪一个最合适？因为对跳数的累加都是1，那么是跳到最远的那个，即下标为i的元素是最优选择吗？不一定。最优选择应该是在能覆盖的这些元素中，挑j+nums[j]的和最大的那个，即跳完这一跳之后下一跳能覆盖最远的那一个。然后，继续循环此过程，直到某一跳能覆盖到最后一个元素了，循环结束。

	public int jump(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return 0;
		}

		int jump = 0;
		int curIdx = 0;
		int jumpIdx = -1;
		while (true) {
			int curVal = nums[curIdx];
			int canReachIdx = Math.min(curIdx + curVal, len-1);
			if (canReachIdx == len-1) {
				jump++;
				break;
			}

			int maxSum = Integer.MIN_VALUE;
			for (int i = curIdx+1; i <= canReachIdx ; i++) {
				int sum = i + nums[i];
				if (sum > maxSum) {
					maxSum = sum;
					jumpIdx = i;
				}
			}

			jump++;
			curIdx = jumpIdx;
		}

		return jump;
	}

在 LeetCode 查看