55. Jump Game

题意：

给一个数组，每个数代表可以跳跃的最大距离，问是否可以跳到终点。

思路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;
}