leetcode-55-Jump Game

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.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

思路1：暴力
没什么好说的，特别慢。用一个数组表示i位置是否可以达到，然后遍历数组，将所有可以达到的位置置1.

bool canJump(vector<int>& nums) { //暴力 特别慢
	int sz = nums.size();
	vector<int> jus(sz, 0);
	jus[0] = 1;
	for (int i = 0; i < sz; ++i)
		if(jus[i])
			for (int j = i + 1; j <= i + nums[i] && j < sz; ++j)
				jus[j] = 1;
	return jus[sz - 1];
}

思路2：动态规划
dp[i]表示前面跳到第i位置时最远还可以多跳多少。
可以得到递推式：dp[i]=max( dp[i - 1], nums[i - 1] )
dp[i]<0表示不能跳到该位置，直接返回false.
时间复杂度O(N),但空间复杂度也是O(N)

#define MAX(A,B) (A>(B)?A:B)

bool canJump(vector<int>& nums) { //动态规划 8ms 99% 空间O(N)
	int sz = nums.size();
	vector<bool> dp(sz, 0);
	for (int i = 1; i < sz; ++i) {
		dp[i] = MAX(nums[i - 1], dp[i - 1]) - 1;
		if (dp[i] < 0)
			return false;
	}		
	return dp[sz - 1] >= 0;
}

思路3：贪心法
使用一个数reach表示目前可以达到的最远距离，当reach >= sz - 1时表示可以达到最后一个位置。
这个方法时间复杂度仍然是O(N)，但空间复杂度仅仅是O(1)

bool canJump(vector<int>& nums) {//贪心8ms 99% 空间O(1)
	int sz = nums.size(), reach = 0;
	for (int i = 0; i < sz; ++i) {
		if (reach < i || reach >= sz - 1)
			break;
		if (reach < nums[i] + i)
			reach = nums[i] + i;
	}
	return reach >= sz - 1;
}