# Leetcode 55. Jump Game
[Leetcode 55. Jump Game](https://leetcode.com/problems/jump-game/description/) (<font color="#FFB800"> Medium</font> 通過率: 38.5%)

## 限制條件
<ul>
<li>1 &lt;= nums.length &lt;= 10^4</li>
<li>0 &lt;= nums[i] &lt;= 10^5</li>
</ul>

### 解法 1
用遞迴的方式寫，逐步找出最後能不能走到。走不到就將逐步走過的點都設定成不能到，這樣可以加快一點速度。

- 時間複雜度: $O(n^2)$
- 空間複雜度: $O(n)$

class Solution {
public:
    bool isJump(vector<int>&amp; nums, int index, vector<bool>&amp; record)
    {
        if(index == nums.size() - 1) return true;
        else
        {
            for(int i = index + 1; i &lt; nums.size() &amp;&amp; i &lt;= index + nums[index] ; i++)
            {
                if(record[i] == true) continue;
                if(isJump(nums, i, record) == true)
                    return true;
                else
                    record[i] = true;
            }
        }
        return false;
    }

    bool canJump(vector<int>&amp; nums) {
        vector <bool> record(nums.size());
        return isJump(nums, 0, record);
    }
};

### 解法 2
用一變數 max_index 來代表某一步之下，能夠走到最遠的距離。用迴圈的方式找在 max_index 之前能不能再找到更大的變數，如果沒有就 return false。如果可以順利走到最後就 return true。

- 時間複雜度: $O(n)$
- 空間複雜度: $O(1)$

class Solution {

public:

    bool canJump(vector<int>&amp; nums) {
        int max_index = nums[0];
        for(int i=0;i</int></bool></int></bool></int>