# 【LeetCode】 55. Jump Game

## Description
> 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:

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.

## Solution

* 一開始還想用BFS...後來發現自己想太多了。
* 你只需要記錄你最遠可以走到哪一格就好，因為你到得了第三格，你也一定可以到第二格。
* 也因為這樣，不需要去想往回跳的情形。
* 這個演算法的缺點是很有可能會跑幾乎整個陣列。因為你還沒跑到時無法得知哪個格子是必要的。

### Code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max = 0;
        for(int i = 0; i <= max; i++)
        {
            max = max < i + nums[i] ? i + nums[i] : max;
            if(max >= nums.size() - 1) return true;
        }
        return false;
    }
};

###### tags: `LeetCode` `C++`