找到到达数组末尾的最小跳跃次数

1. Overview

In this tutorial, we’ll talk about the problem of finding the minimum number of jumps to reach the end of a given array starting from the beginning.

First, we’ll define the problem and provide an example to explain it. Then, we’ll present three different approaches to solving it and work through their implementations and their space and time complexity.

2. Defining the Problem

Suppose we have an array of positive integers, where each element in that array represent the maximum length of the jump we can make to the right. We consider the end of the array as the position after the last element. We were asked to find the minimum number of jumps we could make starting from the first element to reach the end of the array.

Let’s take a look at the following example:

We can reach the end of the given array in multiple ways. Let’s take a look at a few of them:

• .
• .
• .

As we can see, the minimum number of jumps to reach the end of the given array is , where we take the path .

3. Naive Approach

3.1. Main Idea

The main idea in this approach is to try all possible solutions, then get the optimal solution with the minimum number of jumps.

Initially, we’ll have a recursive method to try all the possible solutions. We’ll try to jump to all viable cells from each position with a distance less than or equal to the current element value. Each time we make a call (jump), we increase the number of jumps by one.

Finally, we take the minimum value between all possible calls, representing the minimum number of jumps to reach the end of the given array starting from the current element.

3.2. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm MinimumJumps(A, index):
    // INPUT
    //    A = the given array of positive integers representing the maximum jump length
    //      from each position
    //    index = the current position in the array
    // OUTPUT
    //    The minimum number of jumps to reach the end of the given array
    //      starting from the current position

    if index = length(A):
        return 0

    jumps <- infinity

    for move <- 1 to A[index]:
        if index + move <= length(A):
            next <- MinimumJumps(A, index + move)
            jumps <- Min(jumps, next + 1)

    return jumps

Initially, we declare the function, which will try all possible solutions to reach the end of the given array. The function will have two parameters: The given array , and representing the current position in the array.

First, the base case of the recursive function here is when we reach the end of the array , then we return , the minimum number of jumps to reach the end of the given array starting from the end of the array.

Second, we declare , representing the minimum number of jumps to reach the end of the given array starting from the current position. Initially, its value equals infinity. Then we’ll take the minimum answer among all possible moves we can make. We’ll get the optimal answer for each possible next position starting from that position plus one, which represents the current jump.

Finally, the will return the minimum number of jumps to reach the end of the given array starting from the first element.

3.3. Complexity

The time complexity in the worst case is , where is the length of the given array , and is the maximum value inside the array. For each position in the array, we have choices, which represent the maximum length of jump we can make.

On the other hand, the space complexity of this algorithm is . The reason behind this complexity is that we use a single variable that equals the minimum number of jumps.

4. Dynamic Programming Approach

4.1. Main Idea

The main idea in this approach is the same as the previous one. However, since we have overlapping states, we can use dynamic programming.

Initially, the state of this dynamic programming approach will be , which represents the minimum number of jumps to reach the end of the array starting from the position . Next, since the answer of each state depends on the answers of the next ones, we’ll start calculating the answer of each state starting from the end towards the beginning. Then, for each state , we’ll take the minimum value among all states solution in range .

Finally, the will represent the minimum number of jumps to reach the end of the given array starting from the first position.

4.2. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm MinimumJumps(A):
    // INPUT
    //    A = the array of positive integers where each element represents the maximum length 
    //      of the jump
    // OUTPUT
    //    The minimum number of jumps to reach the end of the array 
    //    starting from the first element

    DP <- initialize an array of length(A) zeroes

    for i <- length(A) - 1 to 0:
        DP[i] <- infinity

        for move <- 1 to A[i]:
            if i + move <= length(A):
                DP[i] <- Min(DP[i], DP[i + move] + 1)

    return DP[0]

Initially, we have the function as the previous approach. It has one parameter , which represents the given array.

First, we declare the array, which will store the minimum number of jumps to reach the end of the array starting from each position.

Second, we set the value of to , which represents the minimum number of jumps to reach the end starting from the end. Next, for each position from the end towards the beginning, we’ll try to jump to the cell with the minimum answer among all the cells in the range .

Finally, the will have the minimum number of jumps to reach the end of the given array starting from the first element.

4.3. Complexity

The time complexity of this algorithm is , where is the length of the given array , and is the maximum length of a jump. The reason behind this complexity is that for each position, we try to make all possible jumps.

The space complexity of this algorithm is , where is the length of the given array . The reason is that we store the minimum number of jumps for each position.

5. Greedy Approach

5.1. Main Idea

The main idea in this approach is to keep moving forward as long as we can. The moment we can’t move, we’ll jump from the cell that takes us as far as possible among all the cells that we’ve passed through.

Initially, in this approach, we care about two things:

1. Maximum reachability: This represents the maximum position we can reach using one of the jumps that we have iterated through.
2. Moves: The number of moves we can make using the last jump we’ve made.

Next, while iterating over the array, we’ll update the maximum position we can reach and decrease the number of moves by one. The moment we run out of moves, we’ll jump from the cell that allows us to reach the maximum position, and we’ll increase the number of jumps by one.

In the end, the number of jumps will be the optimal solution that we could make, and it’ll be the answer to the problem.

5.2. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm MinimumJumps(A):
    // INPUT
    //    A = the given array of positive integers
    // OUTPUT
    //    The minimum number of jumps to reach the end of the array

    maxReach <- A[0]
    moves <- A[0]
    jumps <- 1

    for i <- 1 to length(A) - 1:
        maxReach <- max(maxReach, i + A[i])
        moves <- moves - 1

        if moves = 0:
            jumps <- jumps + 1
            moves <- maxReach - i

    return jumps

Initially, we have the function similarly to the previous approaches.

First, we declare the variable, which will store the maximum position we can reach using the cells that we’ve passed through. Initially, it’s equal to the first element.

Also, We declare the variable, which stores the maximum number of moves we could make using the last jump. Its initial value equals the first element as well. In addition, we declare , which will store the number of jumps we made so far and initially equal one representing the jump from the first element.

Second, we loop through the elements of the given array. In each iteration, we’ll maximize with the next position that uses the maximum length of the current jump. Also, we’ll decrease the number of moves we can make by one. After that, we check whether we run out of . If so, we’ll make a jump using the cell that gets us to the position.

Furthermore, the new value of will equal , because we decide to use the best jump, which should make us reach the position, which needs moves from our current position.

Finally, the will have the minimum number of jumps we need to reach the end of the array starting from the first element.

5.3. Complexity

The time complexity of this algorithm is , where is the length of the given array . This complexity is because we iterate over each position only once.

The space complexity of this algorithm is . The reason is that we have a constant number of variables.

6. Conclusion

In this article, we discussed the problem of finding the minimum number of jumps to reach the end of an array. First, we provided an example to explain the problem. Then, we explored three different approaches to solving it, where each one of them had a better time complexity than the previous one.

Finally, we walked through their implementations and explained the idea behind each of them.