Hello, it’s 2 o ‘clock in the morning. I have just finished my work for the whole day and am busy writing algorithm questions. So today we will continue to explain the algorithm question 55, is also a classic interview question, let’s have a look.

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.

“Example1“

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.
Copy the code

“Example2“

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.
Copy the code

Given an array, the elements in the array represent the number of steps you can jump back. For example, nums[0]=2 means that it can jump back to either nums[1] or nums[2]

So let’s draw a picture to give you an example

I used four different colors to represent the number of steps each element can jump, so it’s pretty clear

Let’s review the ideas of recursion and dynamic programming

  1. “The process of creating an array to store dynamic programming“
  2. “Look for conditions under which recursion ends (you can draw a tree to help you understand)“

So let’s start with dynamic programming what do we have to prepare? What we’re really trying to do is keep a record of whether or not each point jumps to the finish line

We use -1,0,1 to represent three states: “unreachable”, “initialized”, and “reachable”

So let’s initialize the array dp, and set the endpoint to 1, because the endpoint is bound to the endpoint and then let’s think about it a little bit

“What should be the end condition for recursion?“

So let’s draw the recursion


So from this example, our recursion tree would look something like this

Our recursion order is to start with the 1 on the left, go to the right, and finally do the 2 itself, and in this case you’ll see that you can get to the end no matter which way you choose, right? So let’s do a different problem

Let’s draw a dynamic programming table for the following problem

Therefore, our dynamic planning table should look like the one above, with 1 representing reachable paths and -1 representing unreachable paths

So, our recursive end condition should be “dp[I]==-1” or “dp[I]==1” as the end condition

If “dp[I]==0” means that the node has not been evaluated and needs to be recursed again. If the recursion reaches a dead end, we mark the point as -1 and exit

Let’s take a look at the recursive code

func recurrentJump(position int,nums []int, dp *[]int) bool{
	if (*dp)[position] == 1{
		return true
	}else if (*dp)[position] == -1{
		return false
	}
	maxJump := min(position + nums[position], len(nums)-1)
	for i:= position + 1; i<=maxJump; i++{
		result:=recurrentJump(i, nums, dp)
		if result {
			(*dp)[position] = 1
			return true
		}
	}
	(*dp)[position] = -1
	return false
}
func min(x int, y int) int{
	if (x < y){
		return x
	}
	return y
}
Copy the code

The main function of the recursion is above, as we described. If “dp[I]==-1” or “dp[I]==1” is returned, the node has not been evaluated

Let’s look at the loop we need to do when the node is not evaluated

maxJump := min(position + nums[position], len(nums)-1)
for i:= position + 1; i<=maxJump; i++{
	result:=recurrentJump(i, nums, dp)
	if result {
		(*dp)[position] = 1
		return true
	}
}
Copy the code

First of all, find the minimum number of jumps, compare position + nums[I] with nums length, and take the smallest digit that represents the maximum number of jumps that this node can make, and then we recurse, recurse again, all of the jumps that this node can make, okay

If the return value is “true”, this node can jump to the destination, record this node as “dp[position]=1” and return “true”.

Tell the nodes in the upper layer that you can also get to the destination through me, as shown below


And then let’s look at the pivot function

func canJump(nums []int) bool {
	var dp = make([]int, len(nums))
	for i:=0; i<len(nums); i++ {
		dp[i]  = 0
	}
	dp[len(nums)-1] = 1
	ans:= recurrentJump(0, nums, &dp)
	return ans
}
Copy the code

Here, there’s nothing to talk about except initializing the DP array and recursing from subscript 0,

So that’s the recursive +DP algorithm for today, which is not very good, and I’ll write another one tomorrow


Other related topics link

LeetCode 53 – Maximum suborder and – Problem thinking record (with dynamic programming) – GoLang

LeetCode 49 – Letter heterotopic word grouping – Solution record – Golang

LeetCode 21 – Merge ordered lists – Solution record – GoLang

LeetCode 2 – Sum of two numbers – GoLang

LeetCode 12 – Roman numerals – GoLang

LeetCode 15-3 number sum – GoLang

LeetCode 5 – Palindrome string – Solution idea record – GoLang