---
# System prepended metadata

title: 2770. Maximum Number of Jumps to Reach the Last Index
tags: [Leetcode, Dynamic Programming, DFS+Memorization, Medium]

---

Link: https://leetcode.com/problems/maximum-number-of-jumps-to-reach-the-last-index/description/
## 思路
```dp[i]```表示maximum number of jumps to reach the last index from index ```i```
## Code
```python=
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        dp = [-inf]*(len(nums)-1)+[0]
        def dfs(i):
            if dp[i]!=-inf: return dp[i]
            dp[i] = -1
            for j in range(i+1, len(nums)):
                if abs(nums[j]-nums[i])<=target:
                    nextSteps = dfs(j)
                    if nextSteps!=-1: dp[i] = max(dp[i], dfs(j)+1)
            return dp[i]
        return dfs(0)
```