45. Jump Game II

Solution 0: Brute-Force + DP (看完題目第一個想法)

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

Time Complexity: O(N!) // Loop N times * value of nums[i]
Space Complexity: O(N)

Solution 1: DFS (TLE)

class Solution:
    def jump(self, nums: List[int]) -> int:
        def dfs(pos):
            if pos >= len(nums) - 1:
                return 0
                
            minStepJump = 10001
            for jump in range(1, nums[pos] + 1):
                minStepJump = min(minStepJump, 1 + dfs(pos + jump))
            return minStepJump
        
        ans = dfs(0)
        return ans

Time Complexity: O(N!)
Space Complexity: O(N) // Recursive call stack of tree height O(N)

Solution 2: Recursive + DP

Time Complexity: O(N^2)
Space Complexity: O(N)

Solution 3: Iterative DP

Time Complexity: O(N^2)
Space Complexity: O(N)

Solution 4: Greedy

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        maxReachableIdx = 0
        lastJumpedPos = 0
        jumpStepCnt = 0
        for i in range(n - 1):
            # We are already able to jump to the end (n-1) position 
            if lastJumpedPos >= n - 1:
                break
            
            # Furthest idx reachable from current level
            maxReachableIdx = max(maxReachableIdx, i + nums[i])
            # Greedy update (We must jump from the potential position that let us reach the furthest idx)
            if i == lastJumpedPos:
                lastJumpedPos = maxReachableIdx
                jumpStepCnt += 1
        
        return jumpStepCnt

Time Complexity: O(N)
Space Complexity: O(1)

Solution 4-2: Greedy - 2

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/jump-game-ii/discuss/1192401/Easy-Solutions-w-Explanation-or-Optimizations-from-Brute-Force-to-DP-to-Greedy-BFS