055.md

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:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

题意：给定一个没有负数的数组，从索引0开始，索引取出来的值表示当前可以跳的长度范围，比如说是5，那么选择跳1~5个索引位置， 可以跳到最后一个位置返回true，否则返回false

思路

贪心算法：每次选择都选择比当前跳的更远的位置，当前可以跳5格，那么选择跳到哪一个位置呢？？就选择可以跳的比当前更远的位置。

假设当前跳5格，并且当前不能跳到终点，在后五个中，如果每一个位置都不能跳的比当前跳的更远，那么返回false，如果存在跳的

更远的位置，那么才有机会有解。

代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int last = nums.size()-1;    //终点索引
        if(last==0 || last==-1)
            return true;
        
        int begin = 0;    //起跳位置
        
        while(begin<last){
            int num = nums[begin];    //可以跳的长度
            int jump_length = begin+num;     //可以跳到的索引位置
            //可以跳到最后的位置
            if(jump_length>=last) 
                return true;
            
            int i = begin+1;
            //在当前可以跳到的索引位置里面，找出可以跳的比当前更远的位置
            for(;i<=jump_length;++i){
                //跳的比当前远
                if(nums[i]+i>jump_length){
                    begin = i;
                    break;
                }
            }
            //最远只能跳到jump_length,跳不到最后
            if(i>jump_length) 
                return false;
        }
        return true;
        
    }
};