Concise Python DP code, O(n) time


  • 0
    W
    class Solution(object):
        def jump(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n,max_s=len(nums),1000
            if n<=1:
                return 0
            min_s=[max_s for i in range(n)]
            min_s[0]=0
            reach,step,start=0+nums[0],1,1
            while reach<=(n-1):
                x=start
                for i in range(start,reach+1):
                    min_s[i]=step
                    x=max(x,i+nums[i])
                step+=1
                start=reach+1
                reach=x
            return min(step, min_s[n-1])

Log in to reply
 

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