LeetCode 55: Jump Game

Let’s solve LeetCode problem 55 (Jump Game) using dynamic programming. Next week, we’ll consider a sneaky aspect of this problem.

The problem:

You are playing a game on a number line where the aim is to reach position n-1 starting from position 0. As input, you get an array nums of size n containing non-negative integers. From position i, you can move forward any distance between 0 and nums[i] (inclusive). Can you reach the last position to win the game?

Subproblems

To solve a dynamic programming problem, we need to break it down into subproblems and use the subproblems to solve the original problem.

The original problem asks if we can get to position n-1 from position 0. We could answer this by calculating the largest position we can reach from position 0, and checking if it’s at least n-1. Consider a function $f(x)$ that gives us the largest position we can reach from position $x$. Then, if $f(0) \geq n-1$, we win.

If nums[0] is 0, then it’s impossible to win the game. We can’t leave the starting position. But if nums[0] is anything else, we can get from position 0 to positions 1, 2, 3, up to position nums[0]. Using our function $f$, let $a_x =$ nums[x]. Then, if $a_x = 0$, $f(x) = x$. Otherwise, $f(x) = \max(f(x+1), f(x+2), …, f(x+a_x))$.

This definition of $f$ shows us the subproblems: $f(x+1), f(x+2)$, and so on. The subproblems are overlapping because we will need some of the same $f(x)$ values more than once. For example, if we can get from position 0 to positions 1 and 2, then we’ll need the solutions to $f(1)$ and $f(2)$. And if we can get from position 1 to position 2, then we’ll need the solution to $f(2)$ again.

Jump Game has optimal substructure because we can use optimal solutions to the subproblems to find an optimal solution to the original problem. Specifically, we need the largest member of a set of optimal subproblem solutions. Together, overlapping subproblems and optimal substructure are the characteristics of a dynamic programming problem.

Design

As usual, a top-down DP implementation comes naturally from the subproblem analysis. Let’s take the top-down approach.

Let farthest(pos, nums) be a recursive function that returns the farthest point reachable from pos, and let n be the length of nums. There are two base cases to check: if nums[pos] == 0, we will return pos, since we can’t leave position pos. And if pos == n-1 we will return n-1, since we can always get to the last position from itself. After the base cases, we check subproblems farthest(pos+1, nums) through farthest(pos+nums[pos], nums) stopping early if pos reaches the last element of nums.

So far, this is just a recursive solution, not a dynamic programming solution. To get acceptable performance, we will save each farthest result in an array dp of the same size as nums. When possible, we’ll look up the result in dp instead of calling farthest.

Implementation

Here’s a pseudocode implementation:

n = length of nums
define an array dp of size n
dp[n-1] = n-1  // if we get to the last position, we're done

if farthest(0, nums) >= n-1, return true
else return false

farthest(pos, nums)
    n = length of nums
    if nums[pos] == 0, update dp and return pos // base case
    if dp[pos] is defined, return dp[pos]       // memoization

    end = min(n-1, pos + nums[pos])  // stop if we get to the end
    for each i from pos+1 to end
        // update dp if we can get farther
        dp[pos] = max(dp[pos], farthest(i, nums))

    return dp[pos]

Reference

For a Java implementation with some optimizations and a preview of next week’s topic, see Prachi Sharma’s solution on LeetCode.

Thanks to Daniel Zingaro for suggesting an improvement to this article.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.