Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

I will participate in a competition next month, so I thought I could contact more on the topic of dynamic planning, so I found relevant problem sets in Leetcode, and made some problems every day, hoping to lead my teammates to victory rather than defeat in the competition next month.

The title

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

Example 1: input: nums = [2,3,1,1,4] output: true description: you can jump one step from subscript 0 to subscript 1, and then jump three steps from subscript 1 to the last subscript.

Example 2: Input: nums = [3,2,1,0,4] Output: false Explanation: The subscript 3 will be reached anyway. But this subscript has a maximum jump length of 0, so you can never reach the last subscript.

Train of thought

I just did a similar one two days ago. Topic request, can achieve the final goal, we follow the thinking, is starting from the current position, what location, can reach the position marked up to, and then starting from the position of accessible, which could reach a new location, if all can reach position traverse is completed, cannot contain the last a little, that is inaccessible, if included, that is up to. Of course, if you’ve already included the last point, you don’t have to go through it. Simulate example 1: We start at subscript 0, and the only reachable point is 0, which has a value of 2, so our reachable point is [0,2], because 0 is already iterated, we go through 1 and 2, and after iterating 1, we reach 2, 3, 4, which already includes 4, so it must be reachable.

Java version code

class Solution { public boolean canJump(int[] nums) { int len = nums.length; int index = 0; int start = index + 1; int end = index + nums[0]; while (end < len - 1) { if (end < start) { break; } int max = end; for (int i = start; i <= end; i++) { if (i + nums[i] > max) { max = i + nums[i]; }} // start is updated to the next point to start traversal, because 0-end has already been traversed, the next point to be traversed is at least end+1 start = end+1; End = Max; // end = Max; } if (end >= len - 1) { return true; } else { return false; }}}Copy the code