LC-2770 Medium LeetCode

2770. Maximum Number of Jumps to Reach the Last Index

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 31% Topics: Array, Dynamic Programming

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(n)

# dp
class Solution(object):
    def maximumJumps(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [-1]*len(nums)
        dp[0] = 0
        for i in xrange(1, len(nums)):
            for j in xrange(i):
                if abs(nums[i]-nums[j]) <= target:
                    if dp[j] != -1:
                        dp[i] = max(dp[i], dp[j]+1)
        return dp[-1]

Solution from kamyu104/LeetCode-Solutions · MIT