Accepted Python O(n) DP solution


  • 0
    R

    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.


Log in to reply
 

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