# Accepted Python O(n) DP solution

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.