# LeetCode 55 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.

In first solution, i try to search every possible path to the end. return true until found one path. but the solution is too slow.

```
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if(len(nums) < 2):
return True
return self.innerCanJump(nums)
def innerCanJump(self, nums):
if(len(nums) == 0):
return False
if(len(nums) == 1):
return True
for i in range(nums[0]):
if self.innerCanJump(nums[i+1:]):
return True
return False
```

The most important point in this case is how far we can reach, not in which path, so just mark the longest station we can reach and check weather the end point in this range.

```
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
reach = 1
for i in range(len(nums)):
if (reach < i + 1):
break;
reach = max(reach, i + 1 + nums[i])
return reach >= len(nums)
```