# Maximum Number of Jumps to Reach the Last Index
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-jumps-to-reach-the-last-index)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-jumps-to-reach-the-last-index
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** array `nums` of `n` integers and an integer `target`.

You are initially positioned at index `0`. In one step, you can jump from index `i` to any index `j` such that:

* `0 <= i < j < n`
* `-target <= nums[j] - nums[i] <= target`

Return _the **maximum number of jumps** you can make to reach index_ `n - 1`.

If there is no way to reach index `n - 1`, return `-1`.

**Example 1:**

**Input:** nums = [1,3,6,4,1,2], target = 2
**Output:** 3
**Explanation:** To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3. 

**Example 2:**

**Input:** nums = [1,3,6,4,1,2], target = 3
**Output:** 5
**Explanation:** To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5. 

**Example 3:**

**Input:** nums = [1,3,6,4,1,2], target = 0
**Output:** -1
**Explanation:** It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1. 

**Constraints:**

* `2 <= nums.length == n <= 1000`
* `-109 <= nums[i] <= 109`
* `0 <= target <= 2 * 109`

# Approaches
## Brute-Force Recursion
This approach explores all possible valid jump sequences from the starting index 0 to every other index recursively. It calculates the maximum number of jumps for each index by considering all possible previous indices from which a jump could have been made.
**Time:** O(2^n). The recursive function has overlapping subproblems. The number of calls grows exponentially with `n`, leading to a Time Limit Exceeded error on larger inputs. · **Space:** O(n). The space is dominated by the depth of the recursion stack, which can go up to `n` in the worst case.
**Pros:** Conceptually simple and easy to implement.
**Cons:** Extremely inefficient due to redundant computations of the same subproblems.; Will not pass for the given constraints (n <= 1000).
### Explanation
We define a recursive function, let's call it `solve(i)`, which calculates the maximum number of jumps to reach index `i`.
The base case for the recursion is `solve(0)`, which is 0, as we start at index 0 with zero jumps.
For any other index `i`, we iterate through all previous indices `j` (from 0 to `i-1`). If a jump from `j` to `i` is valid (i.e., `abs(nums[i] - nums[j]) <= target`), we recursively call `solve(j)`.
If `solve(j)` returns a valid number of jumps (not -1), it means index `j` is reachable. We then update the maximum jumps to reach `i` as `max(current_max, solve(j) + 1)`.
If no valid jump can be made to index `i`, the function returns -1. The final answer is the result of `solve(n-1)`.
This method is a straightforward translation of the problem's definition into a recursive structure. However, it's highly inefficient because it recomputes the solution for the same subproblems multiple times.
```java
class Solution {
    public int maximumJumps(int[] nums, int target) {
        return solve(nums, target, nums.length - 1);
    }

    private int solve(int[] nums, int target, int currentIndex) {
        if (currentIndex == 0) {
            return 0;
        }

        int maxJumps = -1;
        for (int i = 0; i < currentIndex; i++) {
            // Use long for subtraction to prevent potential integer overflow.
            if (Math.abs((long)nums[currentIndex] - nums[i]) <= target) {
                int prevJumps = solve(nums, target, i);
                if (prevJumps != -1) {
                    maxJumps = Math.max(maxJumps, prevJumps + 1);
                }
            }
        }
        return maxJumps;
    }
}
```
### Algorithm
- Define a recursive function `solve(currentIndex)`.
- Base Case: If `currentIndex` is 0, return 0.
- Initialize `maxJumps = -1`.
- Iterate through all previous indices `i` from 0 to `currentIndex - 1`.
- If a jump from `i` to `currentIndex` is valid and `solve(i)` is not -1, update `maxJumps = max(maxJumps, solve(i) + 1)`.
- Return `maxJumps`.
- The final answer is `solve(n-1)`.

## Top-Down Dynamic Programming with Memoization
This approach optimizes the brute-force recursion by using memoization. We store the results of subproblems in a cache (an array) so that each subproblem is solved only once. This transforms the exponential complexity into a polynomial one.
**Time:** O(n^2). Each state `dp[i]` is computed only once. To compute each state, we iterate through up to `i` previous states. The total work is the sum of `1 + 2 + ... + (n-1)`, which is O(n^2). · **Space:** O(n). We use an O(n) `memo` array and the recursion stack can go up to O(n) deep.
**Pros:** Drastically more efficient than brute-force.; Guaranteed to pass within the time limits.; Maintains a recursive structure which can be intuitive.
**Cons:** Slightly more space usage than the bottom-up approach due to the recursion stack.; Can lead to stack overflow for very large `n` (not an issue here).
### Explanation
The core idea is the same as the recursive approach, but we introduce a `memo` array to store the results. The `memo` array is initialized with a sentinel value (e.g., -2) to indicate that a subproblem has not been computed yet.
When the recursive function `solve(i)` is called, it first checks if `memo[i]` already contains a computed result. If it does, the stored value is returned immediately, avoiding redundant computation.
If the result is not in the memoization table, the function computes it as in the brute-force approach, by checking all possible previous jumps.
Before returning, the computed result for `solve(i)` is stored in `memo[i]`. This ensures that any subsequent call to `solve(i)` will be an O(1) lookup.
This technique is also known as top-down dynamic programming.
```java
import java.util.Arrays;

class Solution {
    private int[] memo;

    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        memo = new int[n];
        // Initialize memo with -2 to distinguish from the result -1 (unreachable).
        Arrays.fill(memo, -2); 
        return solve(nums, target, n - 1);
    }

    private int solve(int[] nums, int target, int currentIndex) {
        if (currentIndex == 0) {
            return 0;
        }
        if (memo[currentIndex] != -2) {
            return memo[currentIndex];
        }

        int maxJumps = -1;
        for (int i = 0; i < currentIndex; i++) {
            if (Math.abs((long)nums[currentIndex] - nums[i]) <= target) {
                int prevJumps = solve(nums, target, i);
                if (prevJumps != -1) {
                    maxJumps = Math.max(maxJumps, prevJumps + 1);
                }
            }
        }
        
        return memo[currentIndex] = maxJumps;
    }
}
```
### Algorithm
- Create a `memo` array of size `n` and initialize it with a sentinel value.
- Define a recursive function `solve(currentIndex)`.
- Base Case: If `currentIndex` is 0, return 0.
- Memoization Check: If `memo[currentIndex]` is not the sentinel value, return it.
- Compute the result as in the brute-force approach.
- Store the computed result in `memo[currentIndex]` before returning.
- The final answer is `solve(n-1)`.

## Bottom-Up Dynamic Programming
This is an iterative dynamic programming approach. We build the solution from the ground up, starting from the base case (index 0) and iteratively computing the solution for all indices up to `n-1`. This avoids recursion and is generally the most efficient implementation for this type of DP problem.
**Time:** O(n^2). We have two nested loops. The outer loop runs `n-1` times, and the inner loop runs up to `n-1` times. · **Space:** O(n). We use an array of size `n` to store the DP states.
**Pros:** Very efficient and passes the given constraints.; Avoids recursion, eliminating the risk of stack overflow and the overhead of function calls.; Often considered the canonical DP solution.
**Cons:** The iterative logic might be slightly less direct to formulate than the recursive top-down approach for some developers.
### Explanation
We use a `dp` array of size `n`, where `dp[i]` will store the maximum number of jumps to reach index `i` from the start.
We initialize `dp[0] = 0` because we are at the starting index with 0 jumps. All other `dp[i]` are initialized to -1 to signify that they are currently unreachable.
We then iterate with an outer loop from `i = 1` to `n-1`. For each `i`, we want to compute `dp[i]`.
To do this, an inner loop iterates through all previous indices `j` from 0 to `i-1`.
Inside the inner loop, we check if index `j` is reachable (`dp[j] != -1`) and if a jump from `j` to `i` is valid (`abs(nums[i] - nums[j]) <= target`).
If both conditions are met, it means we can reach `i` from `j`. The number of jumps would be `dp[j] + 1`. We update `dp[i]` to be the maximum of its current value and `dp[j] + 1`.
After the loops complete, `dp[n-1]` will hold the maximum number of jumps to reach the last index, or -1 if it's unreachable.
```java
import java.util.Arrays;

class Solution {
    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n];
        // Initialize dp array with -1 to represent unreachable states.
        Arrays.fill(dp, -1);
        // Base case: 0 jumps to reach index 0.
        dp[0] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Check if index j is reachable and the jump from j to i is valid.
                if (dp[j] != -1 && Math.abs((long)nums[i] - nums[j]) <= target) {
                    // If so, we can reach i from j. Update dp[i].
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
- Create a `dp` array of size `n`.
- Initialize `dp[0] = 0` and all other elements to -1.
- Loop `i` from 1 to `n-1`.
- Inside, loop `j` from 0 to `i-1`.
- If `dp[j]` is not -1 and a jump from `j` to `i` is valid, update `dp[i] = max(dp[i], dp[j] + 1)`.
- After the loops, return `dp[n-1]`.

# Solutions
### Java

```java
class Solution {
private
  Integer[] f;
private
  int[] nums;
private
  int n;
private
  int target;
public
  int maximumJumps(int[] nums, int target) {
    n = nums.length;
    this.target = target;
    this.nums = nums;
    f = new Integer[n];
    int ans = dfs(0);
    return ans < 0 ? -1 : ans;
  }
private
  int dfs(int i) {
    if (i == n - 1) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int ans = -(1 << 30);
    for (int j = i + 1; j < n; ++j) {
      if (Math.abs(nums[i] - nums[j]) <= target) {
        ans = Math.max(ans, 1 + dfs(j));
      }
    }
    return f[i] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumJumps(vector<int> &nums, int target) {
    int n = nums.size();
    int f[n];
    memset(f, -1, sizeof(f));
    function<int(int)> dfs = [&](int i) {
      if (i == n - 1) {
        return 0;
      }
      if (f[i] != -1) {
        return f[i];
      }
      f[i] = -(1 << 30);
      for (int j = i + 1; j < n; ++j) {
        if (abs(nums[i] - nums[j]) <= target) {
          f[i] = max(f[i], 1 + dfs(j));
        }
      }
      return f[i];
    };
    int ans = dfs(0);
    return ans < 0 ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int: @ cache def dfs(i: int) -> int: if i == n - 1: return 0 ans = - inf for j in range(i + 1, n): if abs(nums[i] - nums[j]) <= target: ans = max(ans, 1 + dfs(j)) return ans n = len(nums) ans = dfs(0) return - 1 if ans < 0 else ans

```