45 Jump Game II

题目

45 Jump Game II

题解

题目要求：给定各个位置中能够跳跃的最大长度，求从起点（第一个下标）跳跃到终点（最后一个下标）的最小跳跃次数。

跳跃的过程是由一次次的跳跃组成的，因此首先对单次跳跃进行分析。对于单次跳跃而言，既需要充分利用起跳位置的跳跃长度，也需要落到一个跳跃长度大的位置。记起跳长度为\(jump\)，落点位置的最大跳跃长度为\(jump_{next}\)，那么对于单次跳跃而言，最佳的落点自然是能够达到最远处的落点，也就是可以使\(jump+jump_{next}\)最大化的那个位置。

上述分析使我们看到使用贪心算法的可能性，即令每一次跳跃都是当前最佳的跳跃。下面对这一做法的正确性进行分析：假设起点为\(p_{start}\)，位置\(p_{start}\)的跳跃长度为\(j_{start}\)，最佳落点为\(p_{best}\)，最佳落点的跳跃长度为\(j_{best}\)；如果我们不选\(p_{best}\)而是选另外的位置\(p_{other}\)（对应的跳跃长度为\(j_{other}\)）作为落点，那么根据选择标准，必然有\(p_{other} + j_{other} \leq p_{best} + j_{best}\)，即\(p_{other}\)能够到达的位置不会比\(p_{best}\)更靠后，这也意味着作为落点\(p_{other}\)不会比\(p_{best}\)更好，\(p_{start}\)到\(p_{best}\)的跳跃为最佳跳跃。如果每次都跳到一个可以最往后靠的位置，那么必然能够以最小跳跃次数到达终点，再结合以上分析，我们就证明了贪心算法的正确性：采用从当前位置进行最佳跳跃的贪心算法能够求出从起点跳跃到终点的最小跳跃次数

代码

class Solution {
public:
	int jump(vector<int>& nums) {
		int position = 0;
		int next_position = 0;
		int count = 0;

		while (position < nums.size() - 1)
		{
			int next_jump;
			int max_jump = 0;
			for (int jump = 1; jump <= nums[position]; jump++)
			{
				if (position + jump >= nums.size() - 1) {
					return count + 1;
				}

				next_jump = nums[position + jump];
				if (jump + next_jump > max_jump) {
					max_jump = jump + next_jump;
					next_position = position + jump;
				}
			}

			position = next_position;
			count++;
		}

		return count;
	}
};