Let **f[i]** be the most remote position a point can reached where the point is before the *ith* position and **r[i]** be the flag whether a point can be reached or not.(**point** here is the element in nums[])

SO

```
f[1] = max(r[0]*(0+a[0]))
f[2] = max(r[0]*(0+a[0]),r[1]*(1+a[1]))
f[3] = max(r[0]*(0+a[0]),r[1]*(1+a[1]),r[2]*(2+a[2]))
# after a simple observation and induction you'll find the following formula
f[i] = max(r[i-1]*(i-1+a[i-1]),f[i-1])
```

*(a[] is the nums[] according to the problem)*

Meanwhile

```
r[1] = 1 if f[1] >= 1 else 0
r[2] = 1 if f[2] >= 2 else 0
r[3] = 1 if f[3] >= 3 else 0
# after a simple observation and induction you'll find the following formula
r[i] = 1 if f[i] >= i else 0
```

Finally my ac code looks like this

```
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
# special case
if n == 0:
return True
f = [0 for i in range(n)]
r = [0 for i in range(n)]
f[0],r[0] = 0,1
for i in range(1,n):
f[i] = max((i-1+nums[i-1])*r[i-1],f[i-1])
r[i] = 1 if f[i] >= i else 0
return True if r[n-1] == 1 else False
```

Time Complexity: O(n)

Space Complexity: O(n)

You may wonder how I come up with this solution.I'll write it later since the place here is insufficient.