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 `nums[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.

(Image credit: DALLĀ·E 3)

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