Start learning free

LESSON 413 OF 667 · MEMOIZATION

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

Practice O(n2) - DP Read the full explanation

You get a vector nums of non-negative integers. You start at index 0.

Return the smallest number of jumps that gets you to the last index.

From index i, you can jump forward any number of steps from 1 to nums[i].

Example 1:

Input: [3,1,4,1,1,2,1]
Output: 2
Explanation: Jump 2 steps, from index 0 to index 2.
Then jump 4 steps, from index 2 to index 6, the last index.
Both jumps are allowed: nums[0] = 3 and nums[2] = 4.

Example 2:

Input: [1,2,1,1,1]
Output: 3
Explanation: The best route is 0 → 1 → 3 → 4.

Example 3:

Input: [6,2,1]
Output: 1
Explanation: A jump can be shorter than nums[i].
One jump of 2 steps goes from index 0 to the last index.

Constraints:

  • 1 to 110,000 numbers.
  • Each number is from 0 to 1,000.
  • The last index can always be reached.

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
    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

    1. 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.
    2. Set the last entry to 0. The last index needs no jumps.
    3. 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.
    4. 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.
    5. Relax the entry. dp[i] = min(dp[i], 1 + dp[j]) keeps the cheapest first jump found so far.
    6. 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++650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free