Little Dom is almost a year old, and although he can’t walk yet, he’s already itching to jump. Now Little Dom wants to know if he can jump from one end to the other in a finite number of steps.

To help Little Dom solve this problem, today we’re going to look at the “jump game” problem in algorithms.

The rules of the jumping game question are as follows:

  • Given an array of non-negative integers, you start at the first position in the array.
  • Each element in the array represents the maximum length you can jump at that location.
  • Determine if you can reach the last position in the array.

Dom needs to figure out can we get to the last place in the array?

Example 1 is as follows:

Input: [2,3,1,1,4] output: true explanation: jump 1 step from position 0 to position 1, then jump 3 steps from position 1 to the last position.Copy the code

Example 2 is as follows:

Input: [3,2,1,0,4] Output: false Explanation: No matter how you jump, you will always reach position 3, but that position has a maximum jump length of 0, so you will never reach the last position.Copy the code

This is the “jump game” problem in the algorithm. Do you, the smart one, know how to help Little Dom solve this problem?