Prompt: Given an array of non-negative integers, each of the integers represents the range that it can jump to the right of the array. Determine if we can jump successfully from the start of the array to the end of the array.
Example:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Solution: This problem can be broken down into subproblems where a subproblem could be could any of the previous jumps allowed you to jump to the current spot. Knowing this, we can use bottom up tabulation to find out if we can jump to a certain spot depending on previous spots.
First, we need a tabularized version, dp, of the original and initialize it with False. Then, we can loop through every position in the array. For the current position, we can determine if we can jump to the current position with two conditions:
- if we can jump to a previous position
- if that previous position has the range to jump to the current position.
By the end, we can just return the last element of dp as the answer.