45. Jump Game II - cocoder39/coco39_LC GitHub Wiki

45. Jump Game II

Greedy is hard to understand and code. Solution below is like a recursive version of bfs where left and right define reachable range within this level/steps

class Solution:
    def jump(self, nums: List[int]) -> int:
        left, right = 0, 0
        steps = 0
        while right < len(nums) - 1:
            steps += 1
            oldRight = right
            for i in range(left, oldRight+1):
                right = max(right, i+nums[i])
            left = oldRight + 1
        return steps

=====================

Greedy T = O(N)

There is a BFS structure. maxPos is the last index at cur level. maxPos is the furthest reachable position at cur level. once i == maxStep we reach the end of cur level. The end of next level is maxPos

class Solution:
    def jump(self, nums: List[int]) -> int:
        jump = maxPos = maxStep = 0
        n = len(nums)
        
        for i in range(n):
            if maxStep >= n-1:
                break
                
            maxPos = max(maxPos, i + nums[i])
            if i == maxStep:
                jump += 1
                maxStep = maxPos
                
        return jump

DP T = O(n^2)

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] + [float("inf")] * (n-1)
        
        for i in range(1, n):
            for j in range(i):
                if j + nums[j] >= i:
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]