jump-game-ii.md

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index. My code: O(n^2) not enough

import numpy as np
import time
class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        self.record=np.zeros(len(nums))-1
        count=self.jump_count(nums,0)
        return int(count)
    def jump_count(self,nums,i):
        if i>=len(nums)-1:
            return 0
        if self.record[i]!=-1:
            return int(self.record[i])
        print('checked i %d'%i)
        max_jump=nums[i]
        min_value=99999
        j=max_jump-1
        while j>=0:
            use_jump=1+self.jump_count(nums,i+j+1)
            if use_jump<min_value:
                min_value=use_jump
            if min_value==1 and i==0:
                return 1
            j=j-1
        self.record[i]=min_value
        return int(self.record[i])
SOLU=Solution()
i=25000
nums=[]
while i>0:
    nums.append(i)
    i=i-1
nums.append(1)
nums.append(0)
result=SOLU.jump(nums)
print(result)   

Solution: Greedy can work on O(n)

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1: return 0
        i = level = far = next_far = 0
        while True:
            while i <= far:
                next_far = max(nums[i] + i, next_far)
                if next_far >= len(nums) - 1:
                    return level + 1
                i += 1
                
            far = next_far
            level += 1