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?