Is there a route to the end of the jump table?

Question

I'm currently learning about Dynamic Programming and solving a "coding question" related to the topic.

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true

Example 2:

Input: [3,2,1,0,4]
Output: false

Here's my code:

    def canJump(nums: List[int]) -> bool:
        memo = {len(nums) - 1: True}
        def canJumpPos(pos):
            if pos >= len(nums):
                return False
            elif pos in memo:
                return memo[pos]
            else:
                for i in range(nums[pos], 0, -1):
                    if canJumpPos(i + pos):
                        return True
                memo[pos] = False
        
        return canJumpPos(0)

I'm having trouble reasoning about the time/space complexity of my approach. My understanding is that without memoization, this approach would be exponential. But, with memoization, this becomes a linear time algorithm? Is this correct? How would you recommend I calculate time complexity in the future when I'm dealing with dynamic programming?

Answer 1

All paths do not return

    def canJumpPos(pos):
        if pos >= len(nums):
            return False
        elif pos in memo:
            return memo[pos]
        else:
            for i in range(nums[pos], 0, -1):
                if canJumpPos(i + pos):
                    return True
            memo[pos] = False
            # Missing Return

This means canJump([3,2,1,0,4]) returns None, not False! A violation of your declared -> bool return.

No memoization of True

When this code returns True:

                if canJumpPos(i + pos):
                    return True

memo[pos] is never set to True. This means that if canJumpPos(pos) is called called with the same pos value, it will have to redo all the work it has already done to return the same True value!

Eschew offset additions, assiduously

            for i in range(nums[pos], 0, -1):
                if canJumpPos(i + pos):

Here, you are always using i + pos, never i by itself. Instead of repeating this addition over and over again, you could roll that addition into the range() end-points.

            for i in range(nums[pos] + pos, pos, -1):
                if canJumpPos(i):

Any and All

Looping over some condition until you find a True condition:

            for i in range(nums[pos] + pos, pos, -1):
                if canJumpPos(i):
                    return True
            # ...

is often better performed using any(...):

            if any(canJumpPos(i) for i in range(nums[pos] + pos, pos, -1)):
                return True
            # ...

The any(...) will terminate when the first True is found, and return True. If no True value is found, it will return False.

There is a similar function all(...), which will terminate at the first False returning False. If no False value is found, it returns True.