Skip to content

2770. Maximum Number of Jumps to Reach the Last Index 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int maximumJumps(vector<int>& nums, int target) {
    const int n = nums.size();
    // dp[i] := the maximum number of jumps to reach i from 0
    vector<int> dp(n, -1);
    dp[0] = 0;

    for (int j = 1; j < n; ++j)
      for (int i = 0; i < j; ++i)
        if (dp[i] != -1 && abs(nums[j] - nums[i]) <= target)
          dp[j] = max(dp[j], dp[i] + 1);

    return dp[n - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int maximumJumps(int[] nums, int target) {
    final int n = nums.length;
    // dp[i] := the maximum number of jumps to reach i from 0
    int[] dp = new int[n];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    for (int j = 1; j < n; ++j)
      for (int i = 0; i < j; ++i)
        if (dp[i] != -1 && Math.abs(nums[j] - nums[i]) <= target)
          dp[j] = Math.max(dp[j], dp[i] + 1);

    return dp[n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maximumJumps(self, nums: list[int], target: int) -> int:
    n = len(nums)
    # dp[i] := the maximum number of jumps to reach i from 0
    dp = [-1] * n
    dp[0] = 0

    for j in range(1, n):
      for i in range(j):
        if dp[i] != -1 and abs(nums[j] - nums[i]) <= target:
          dp[j] = max(dp[j], dp[i] + 1)

    return dp[-1]