LESSON 292 OF 409 · MEMOIZATION

Jump Game in C++: Minimum Jumps with Bottom-Up DP in O(n^2)

Practice O(n²) - DP Read the full explanation

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
             Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

Convert the previous solution to an iterative one. Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

C++ · MEMOIZATION

Jump Game in C++, explained

Problem overview

The method jump(vector<int>& nums) receives non-negative integers. You start at index 0, and nums[i] is the maximum length of a jump from index i: you may jump any distance from 1 up to nums[i] to the right. The method returns the minimum number of jumps needed to reach the last index.

For [2, 3, 1, 1, 4] the answer is 2: jump 1 step from index 0 to index 1, then 3 steps to index 4. No single jump works, because nums[0] is only 2.

This is the third lesson on the problem. The note asks you to turn the earlier recursive solution into an iterative one running in O(n²) time with O(n) extra space. This article covers only that bottom-up version.

Approach: work out the answer for each index from the right

Let dp[i] be the minimum number of jumps needed to get from index i to the last index. The answer is dp[0].

The last index needs 0 jumps. For any earlier index i, the first jump lands on some j between i + 1 and i + nums[i]. That jump costs 1, and then you need dp[j] more. So:

dp[i] = 1 + min(dp[j])   for every j in i+1 .. i+nums[i]  (and j inside the array)

Every dp[i] depends only on entries to its right. If the loop goes from the right end down to index 0, those entries are already final when they are needed. A top-down recursion computes the same values by asking for them on demand; the loop computes them in a fixed order and avoids the recursion entirely.

For [2, 3, 1, 1, 4] the table fills like this, from the right:

dp[4] = 0, the last index.
dp[3]: from index 3 the only reachable index is 4, so dp[3] = 1 + 0 = 1.
dp[2]: only index 3 is reachable, so dp[2] = 1 + 1 = 2.
dp[1]: indices 2, 3 and 4 are reachable, and the best is index 4, so dp[1] = 1.
dp[0]: indices 1 and 2 are reachable, and 1 + dp[1] = 2 beats 1 + dp[2] = 3, so dp[0] = 2.

The finished table is [2, 1, 2, 1, 0].

Step by step

Create the table. vector<int> dp(nums.size(), nums.size()) fills every entry with nums.size(). A real answer is at most n - 1 jumps, so this value acts as "infinity" until a real path is found.
Set the last entry to 0. The last index needs no jumps.
Loop i from the second-to-last index down to 0 with --i and the condition i >= 0. The variable must be a signed int.
Loop j over the cells reachable from i: from i + 1 while j < nums.size() and j <= i + nums[i]. The first test keeps a long jump from running past the end of the vector.
Relax the entry. dp[i] = min(dp[i], 1 + dp[j]) keeps the cheapest first jump found so far.
Return dp[0].

The solution in C++

class Solution {
public:
    int jump(vector<int> &nums) {
        vector<int> dp(nums.size(), nums.size());
        dp[nums.size() - 1] = 0;
        for (int i = nums.size() - 2; i >= 0; --i) {
            for (int j = i + 1; j < nums.size() && j <= i + nums[i]; ++j) {
                dp[i] = min(dp[i], 1 + dp[j]);
            }
        }
        return dp[0];
    }
};

C++ details worth checking:

Why i is an int. With an unsigned index (such as size_t), i >= 0 is always true and --i at 0 wraps around to a huge number, so the loop never ends. The signed int goes to -1 and stops.
A vector of size 1. nums.size() - 2 is computed in unsigned arithmetic and wraps to a huge value. Assigning it to an int turns it back into -1 on common platforms, so the outer loop is skipped and the function returns dp[0] = 0. This works, but it relies on that conversion. Writing int n = nums.size(); first makes the arithmetic signed.
The two-argument constructor. vector<int>(count, value) creates count copies of value.
Mixed comparisons. j < nums.size() compares an int with an unsigned value. That is safe here because j is never negative.

Complexity

Time: O(n²). For each of the n indices, the inner loop can visit up to n - i - 1 cells, so the total is at most about n²/2 steps.

Space: O(n). The dp table holds one integer per index.

A greedy approach reaches O(n) time and O(1) space: scan once, track the farthest index reachable with the current number of jumps, and add a jump each time the scan reaches the end of the current range. This lesson practises the dynamic-programming version first, and it is the one that extends to variations in which the cost of a jump is not always 1.

Edge cases and common mistakes

One element. [0] already stands on the last index, so the answer is 0.
A zero in the middle. [2, 3, 0, 1, 4] still gives 2: index 0 jumps to index 1, which jumps to index 4. Zeros only matter if every path hits one.
Unreachable end. For [1, 0, 1], the table keeps the "infinity" value, so the function returns 3, which is not a real jump count. The lesson's inputs always allow reaching the end, but a count of nums.size() or more means the end cannot be reached.
Overlong jumps. Without the test j < nums.size(), an index such as i + nums[i] beyond the end would read outside the vector, which C++ does not catch.
Using 0 as "infinity". Starting the table at 0 makes min always pick 0, so every answer is wrong. The starting value has to be larger than any real answer.

Testing

[2, 3, 1, 1, 4] gives 2.
[0] gives 0.
[1, 1, 1, 1] gives 3.
[3, 2, 1] gives 1.
[2, 3, 0, 1, 4] gives 2.

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free