Interview Classic 150 Problem 45: Jump Game II

---

Timeline

Timeline

2025-10-02

init

Greedy, Dynamic Programming

---

Problem:

P45 Jump GameII

https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

The first thing that came to my mind is dynamic programming
Let dp[i] represent the minimum number of jumps to reach i, -1 means unreachable. Then for 0 <= j < i, if j can reach i, i.e., nums[j] + j >= i and dp[j] != -1

$$dp[i] = min (dp[j] +1)$$

If there is no such j that is reachable, then

$$dp[i] = -1$$

#include <climits>
#include <vector>
using std::vector;

class Solution {
public:
  int jump(vector<int> &nums) {
    // dp[i] represents the minimum number of jumps to reach i, -1 means unreachable
    // For 0 <= j < i
    // if(nums[j] + j >= i ) dp[i] = dp[j] + 1;
    // If no such j exists, dp[i] = -1;
    int n;
    int min;
    n = nums.size();
    vector<int> dp(n, -1);

    dp[0] = 0;
    for (int i = 1; i < n; i++) {
      min = INT_MAX;
      for (int j = 0; j < i; j++) {
        if (nums[j] + j >= i && dp[j] != -1 && dp[j] + 1 < min) {
          min = dp[j] + 1;
        }
      }
      if (min != INT_MAX) {
        dp[i] = min;
      } else {
        dp[i] = -1;
      }
    }
    return dp[n - 1];
  }
};

This problem is actually a classic greedy problem. Looking from the end, the last position must have been jumped from some previous position, but there may be multiple such positions. Then we greedily choose the farthest one (because it’s one more jump anyway, choosing the one closer to the start will definitely reduce the number of jumps. This is because if two points can both reach the last position, with a being earlier and b being later, we will definitely choose a, since the steps to reach a are less than or equal to those to reach b). After choosing, the selected position becomes the new last position.

class Solution {
public:
    int jump(vector<int>& nums) {
        int position = nums.size() - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
};

You can also modify it using the idea of the following problem

P55 Jump Game

https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

Official solution:

If we greedily search forward, each time finding the farthest reachable position, we can obtain the minimum number of jumps in linear time.

For example, for the array [2,3,1,2,4,2,3], the initial position is index 0. Starting from index 0, the farthest reachable index is 2. Among the positions reachable from index 0, the value at index 1 is 3, and starting from index 1 can reach a farther position, so the first step reaches index 1.

Starting from index 1, the farthest reachable index is 4. Among the positions reachable from index 1, the value at index 4 is 4, and starting from index 4 can reach a farther position, so the second step reaches index 4.

fig1

In the specific implementation, we maintain the maximum index position that can be reached currently, called the boundary. We traverse the array from left to right, and when we reach the boundary, we update the boundary and increase the jump count by 1.

When traversing the array, we do not visit the last element, because before visiting the last element, our boundary must be greater than or equal to the last position, otherwise we cannot jump to the last position. If we visit the last element, when the boundary is exactly the last position, we will add an ‘unnecessary jump count’, so we do not need to visit the last element.

class Solution {
public:
    int jump(vector<int>& nums) {

        int i = 0, j = 0, n = nums.size();

        int max_pos = 0;
        int last_end = 0;
        int step = -1;

        for(i = 0; i< n;i++){
            max_pos = std::max(max_pos, i + nums[i]);
            if(i == last_end){
                last_end = max_pos > n-1 ? n-1: max_pos;
                step++;
            }
        }
        return step;

    }
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        int jump(vector<int> &nums)
        {
                // Jump from back to front, greedily choose the farthest one that can jump over
                int i, n = nums.size();
                int curr = n - 1;
                int cnt = 0;

                while (curr > 0) {
                        for (i = 0; i < curr; i++) {
                                if (nums[i] + i >= curr){
                                        curr = i;
                                        cnt++;
                                        break;
                                }

                        }
                }

                return cnt;
        }
};