**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

1 | Input: [2,3,1,1,4] |

1 | Input: [3,2,1,0,4] |

#### Solution

##### Dynamic Programming

The basic thought is to think from the last position, the last one can definitely reach itself. So let’s make `dp[n-1] = True`

, `dp[i]`

means whether it can reach the end from index `i`

.

`dp[i] = any(dp[i:i + nums[i]])`

`any()`

means if there exists one ore more `True`

.

I came up with this solution in five minutes, but, unfortunately, `Time Limit Exceed`

, that’s what I got.

###### Algorithm

*Python*

1 | def canJump(s): |

###### Complexity

- Time Complexity: O(N^2)
- Space Complexity: O(N)

##### Greedy

We have a variable to store the last position that can reach the end, we track from the end of the array, so `lastPos = n - 1`

at the beginning. When we have `i + s[i] >= lastPos`

, we can know we can reach the end step by step from index `i`

. At the same time, we need to update `lastPos`

to `i`

. At the end, we can just check whether `lastPos == 0`

.

###### Algorithm

*Python*

1 | def canJump(s): |

###### Complexity

- Time Complexity: O(N)
- Space Complexity: O(1)