**Solution with discussion**https://discuss.leetcode.com/topic/80174/python-solution-with-detailed-explanation

**Jump Game** https://leetcode.com/problems/jump-game/?tab=Description

**Memoization Solution**

- Draw the recursion tree. Notice we can have stack overflow for an exremely large input. MLE

```
class Solution(object):
def canJump(self, nums):
return self.can_jump_memoization(0, nums, {})
def can_jump_memoization(self, i, array, cache):
"""
:type nums: List[int]
:rtype: bool
"""
if i >= len(array):
return False
elif i == len(array)-1:
return True
elif i in cache:
return cache[i]
else:
cache[i] = False
for j in range(1, array[i]+1):
if self.can_jump_memoization(j+i, array, cache):
cache[i] = True
return True
return cache[i]
```

**Dynamic Programming Solution**

- Complexity is order n^2. We have an issue here - TLE.

```
class Solution(object):
def canJump(self, nums):
dp = [False]*len(nums)
dp[0] = True
for i in range(1,len(nums)):
for j in range(i-1,-1,-1):
if dp[j] == True and nums[j] + j >= i:
dp[i] = True
break
return dp[-1]
```

**Linear - Ladders and Stairs Solution**

- Linear complexity

```
class Solution(object):
def canJump(self, nums):
max_reach = nums[0]
end_index = len(nums)-1
if max_reach >= end_index:
return True
for i in range(1, len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i+nums[i])
if max_reach >= end_index:
return True
return False
```

```
class Solution(object):
def canJump(self, nums):
max_reach, i, N = 0, 0, len(nums)
while i < N and max_reach >= i:
max_reach = max(max_reach, i+nums[i])
if max_reach >= N-1:
return True
i += 1
return False
```