Cacher is the code snippet organizer for pro developers

# Time complexity: O(n)

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return 0
        n = len(nums)
        reachIdx = nums[0]
        preReachIdx = 0
        step = 1
        while reachIdx < n-1:
            newReachIdx = 0
            for idx in range(preReachIdx+1, reachIdx+1):
                newReachIdx = max(newReachIdx, nums[idx]+idx)
            # New reachIdx = the max `nums[idx]+idx` from preReachIdx+1(including) to reachIdx(including),
            # and then preReachIdx = old reachIdx.
            # Note that [preReachIdx] is not included in the new reach idx evaluation.
            step += 1
            preReachIdx = reachIdx
            reachIdx = newReachIdx
        
        return step

# dp will encounter Time Limit Exceeded error for time complexity: O(n*avg(nums))

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return 0
        
        n = len(nums)
        steps = [float('inf')] * n
        steps[n-1] = 0
        for curIdx in range(n-2,-1,-1):
            varStart = curIdx + 1
            varEnd = min(n-1, curIdx+nums[curIdx])
            if varStart == varEnd+1:
                continue
            steps[curIdx] = min(steps[varStart:varEnd+1]) + 1
        print steps
        return steps[0]