Solutions

# DFS with memoization, bottom-up DP (from right to left), or greedy (left to right reachable range)
# greedy

# Top-down DP - O(n^2) time, O(n) space
def jump(nums: list[int]) -> int:
    dp = {}

    def dfs(i: int) -> int:
        if i == len(nums)-1:
            return 0
        elif nums[i] == 0:
            return 99999
        elif i in dp:
            return dp[i]

        n = nums[i]
        end = min(len(nums) - 1, i + n)
        res = 99999
        for j in range(i + 1, end + 1):
            res = min(res, 1 + dfs(j))

        dp[i] = res
        return res

    return dfs(0)
    
# Bottom-up DP - O(n^2) time, O(n) space
def jump(nums: list[int]) -> int:
    N = len(nums)
    dp = [9999] * N
    dp[N-1] = 0

    for i in range(N-2, -1, -1):
        # dp[j]: minimum number of jumps needed to reach the last index from j
        farthest = min(N-1, i + nums[i])

        for j in range(i+1, farthest + 1):
            dp[i] = min(dp[i], dp[j] + 1)

    return dp[0]


# Greedy ("BFS") - O(n^2) time, O(1) space
def jump(nums: list[int]) -> int:
    res = 0
    l, r = 0, 0

    while r < len(nums)-1:

        farthest = 0
        for i in range(l, r+1):
            farthest = max(farthest, i + nums[i])

        l = r+1
        r = farthest
        res += 1

    return res