leetcode

commit 68396b3ff8165a96bb3f20b2c82a7c832fdb500a
parent 910ac6fb957ed6912f2c5f8a3fe1a3a148152c4e
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 10 May 2026 10:25:42 -0600

2770. maximum number of jumps to reach the last index

Diffstat:
A
max_num_jumps_last_idx.c
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++
A
max_num_jumps_last_idx.py
 | 
34
++++++++++++++++++++++++++++++++++

2 files changed, 80 insertions(+), 0 deletions(-)
diff --git a/max_num_jumps_last_idx.c b/max_num_jumps_last_idx.c
@@ -0,0 +1,46 @@
+// 2770. Maximum Number of Jumps to Reach the Last Index
+#include "leetcode.h"
+
+/*
+ * you are given an 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 index 'j' such that '0 <= i < j < n' and '-target <=
+ * nums[j] - nums[i] <= target'. return the maximum number of jumps you can make
+ * to reach each index 'n - 1'. if there is no way to reach index 'n - 1',
+ * return -1.
+ */
+
+int dfs(int i, int *nums, int n, int target, int *memo) {
+  if (i == n - 1)
+    return 0;
+  if (memo[i] != INT_MIN)
+    return memo[i];
+  int res = INT_MIN;
+  for (int j = i + 1; j < n; j++)
+    if (abs(nums[i] - nums[j]) <= target)
+      res = fmax(res, dfs(j, nums, n, target, memo) + 1);
+  memo[i] = res;
+  return res;
+}
+
+int maximumJumps(int *nums, int numsSize, int target) {
+  int *memo = (int *)malloc(numsSize * sizeof(int));
+  for (int i = 0; i < numsSize; i++)
+    memo[i] = INT_MIN;
+  int ans = dfs(0, nums, numsSize, target, memo);
+  free(memo);
+  return ans < 0 ? -1 : ans;
+}
+
+int main() {
+  int nums[] = {1, 3, 6, 4, 1, 2};
+  int r1 = maximumJumps(nums, ARRAY_SIZE(nums), 2);
+  int r2 = maximumJumps(nums, ARRAY_SIZE(nums), 3);
+  int r3 = maximumJumps(nums, ARRAY_SIZE(nums), 0);
+  printf("%d\n", r1);
+  assert(r1 == 3);
+  printf("%d\n", r2);
+  assert(r2 == 5);
+  printf("%d\n", r3);
+  assert(r3 == -1);
+}
diff --git a/max_num_jumps_last_idx.py b/max_num_jumps_last_idx.py
@@ -0,0 +1,34 @@
+# 2770. Maximum Number of Jumps to Reach the Last Index
+from typing import List
+
+"""
+you are given an 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 index 'j' such that '0 <= i < j < n' and '-target <=
+nums[j] - nums[i] <= target'. return the maximum number of jumps you can make
+to reach each index 'n - 1'. if there is no way to reach index 'n - 1',
+return -1.
+"""
+
+
+class Solution:
+    def maximumJumps(self, nums: List[int], target: int) -> int:
+        def dfs(i: int):
+            if i == len(nums) - 1:
+                return 0
+
+            res = float("-inf")
+            for j in range(i + 1, len(nums)):
+                if abs(nums[i] - nums[j]) <= target:
+                    res = max(res, dfs(j) + 1)
+            return res
+
+        ans = dfs(0)
+        return -1 if ans < 0 else ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=2))
+    print(obj.maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=3))
+    print(obj.maximumJumps(nums=[1, 3, 6, 4, 1, 2], target=0))