LeetCode55-跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

一、思路

（一）回溯法

回溯法可以列出所有的可能，因此一定能够正确的解决这个问题

C++代码：

class Solution {
public:
	bool flag;
	bool canJump(vector<int>& nums) {
		flag = false;
		recall(nums, 0);
		return flag;
	}
	void recall(vector<int> nums, int pos) {
		if (pos == nums.size() - 1) {
			flag = true;
			return;
		}
			
		if (pos > nums.size() - 1)
			return;

		if (nums[pos] == 0)
			return;

		int next;
		for (int i = 1; i <= nums[pos]; i++) {
			next = pos + i;
			if (next > nums.size() - 1)
				return;
			recall(nums, next);
			next -= i;
		}
	}
};

然而：

超时了

（二）改进回溯法

我们先来看看这个超时数据：

[8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5]

在运行回溯算法的时候，我们总是一步一步的尝试，不放过任何一个可能，但是从这个数据来看，这么做有什么问题呢？

上面的nums[0]=8，我们这里以nums[0]=2进行分析：
那么就有8个选择：
（1）走1格，到nums[1]=2

• 再走1格，到nums[2]=4
• 再走2格，到nums[3]=4

（2）走2格，到nums[2]=4

• 再走1格，到nums[3]=4
• 再走2格，到nums[4]=4
• 再走3格，到nums[5]=9
• 再走4格，到nums[6]=5

来看看，有多少种可能的情况：
nums[2]=4
nums[3]=4
nums[4]=4
nums[5]=9
nums[6]=5
只有5种，其中nums[2]=4、nums[3]=4重复了一次，也就是说走1格这种选择已经被走2的完全覆盖了

如果第一次走3格：
（3）走3格，到nums[3]=4

• 再走1格，到nums[4]=4
• 再走2格，到nums[5]=9
• 再走3格，到nums[6]=5
• 再走4格，到nums[7]=2

实际上，我们只要走的尽可能的远就行了，远到超过数组长度，就可以直接返回true啦

也就是说每次都要找到最远路径，那么是不是每次都取最大长度呢？
下面这个数据告诉我们似乎也不是这样

[3,1000,1,2,0,0,5]

那么是选择将两次的步数加起来最大的那个吗？
下面给出一张示意图：

这么来看这个想法是正确的，至少它在局部上来说是最优的

于是算法流程如下
（1）寻找下一步所有可能的选择中，下标+可移动步数 最大的那个，将其作为下一步的移动目标，并移动到那里
（2）重复（1）直到抵达终点或者所选位置的可移动步数=0，终止算法

C++代码：

class Solution {
public:
	bool canJump(vector<int>& nums) {
		if (nums.empty() || nums.size() == 1)
			return true;

		bool flag = false;
		int len, max = 0;
		int next, pos = 0;
		while (pos < nums.size() - 1) {
			if (pos + nums[pos] >= nums.size() - 1) {
				flag = true;
				break;
			}

			if (nums[pos] == 0)
				break;

			max = 0;
			for (int i = 1; i <= nums[pos]; i++) {
				len = i + pos + nums[i + pos];
				if (len > max) {
					max = len;
					next = i + pos;
				}
			}
			pos = next;
		}
		return flag;
	}
};

执行效率：