1. 055
2. 算法
http:\/\/www.acmerblog.com\/leetcode-solution-jump-game-6217.html
http:\/\/www.cnblogs.com\/grandyang\/p\/4371526.html
2.1 贪心算法：O（n）- 正向
正向，从0出发，一层一层网上跳，看最后能不能超过最高层，能超过，说明能到达，否则不能到达。
2.2 贪心算法：O(n):反向
- 逆向，从最高层下楼梯，一层一层下降，看最后能不能下降到第0层。
2.3 DP:O(n)
维护数组dp，dp[i]是走到i位置时，剩余的最大步数
递推：dp[i]=max(dp[i-1,A[i-1]])-1
若：dp[i]是负数，返回false
最后判断dp数组的最后一位是否是负数
3. 代码
3.1 正向贪心
class Solution{
public:
bool canJump(vector<int>& nums){
int n=nums.size();
int reach=1; // 最右可以跳到哪里
for(int i=0;i<reach && reach<n ;++i){
reach=max(reach,i+1+nums[i]);
}
return reach>=n;
}
};
3.2 逆向贪心
class Solution {
public:
bool canJump (int A[], int n) {
if (n == 0) return true;
// 逆向下楼梯，最左能下降到第几层
int left_most = n - 1;
for (int i = n - 2; i >= 0; --i)
if (i + A[i] >= left_most)
left_most = i;
return left_most == 0;
}
};
3.3 DP
// LeetCode, Jump Game
// 思路三，动规，时间复杂度O(n)，空间复杂度O(n)
class Solution{
public:
bool canJump(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n,0);
for(int i=1;i<n;i++){
dp[i]=max(dp[i-1],nums[i-1])-1;
if(dp[i]<0) return false;
}
return dp[n-1]>=0;
}
};