1. 055

jump-game

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;

    }
};