Hello, everyone, I again to share the algorithm topic, careful friends should be able to see this time the picture is more beautiful yes, is because the previous approach feels too casual, and not beautiful enough for a programmer how can so no requirements?

Incidentally, attach the code address on GitHub :LeetCode code collection – constantly updated

Let’s think about last night’s example

If you haven’t read this article, be sure to check out a plane ticketLeetCode 55 – Jump Games – Solution Notes (Recursion + Dynamic programming) – Golang

This lecture will focus on examples of recursion and dynamic programming, so the obvious question is… It’s extremely inefficient and there’s nothing we can do to make it more efficient?

So today to explain the other two ideas “1. Dynamic programming” “2. Optimized version of dynamic programming (optimization is the space complexity)” that we will follow this idea to go down, first to understand the algorithm of dynamic programming to replace the recursive algorithm

Dynamic programming edition

You should forget that dynamic programming requires a table to store past records, and in this algorithm, we still need to use this array

So the way to do it is not to use recursion, do it with a for loop, and let’s keep looking at the code

func nonRecurrentJump(nums[] int, dp *[]int) bool{
 for i:= len(nums)2 -; i>=0; i-- {  maxJump := min(i+nums[i], len(nums)- 1) // Get the number of jump steps
  for j := i + 1; j<=maxJump; j++{
   if (*dp)[j] == 1{
 (*dp)[i] = 1  break  }  }  }  if (*dp)[0] = =1{  return true  }  return false } Copy the code

In this algorithm, it’s very similar to the recursive algorithm, except that in the second For loop, instead of going into the recursion, we’re going directly to see if dp[j]==1 is true. In this code, we’ve actually changed our thinking. The idea of recursion is to start from the beginning, whereas in this code we’re going backwards

Let’s simplify it a little bit, going from needs to“dp[len(nums)-1]“become“dp[len(nums)-i]“ 个

Because if we can get there“2“This element, which means we can get to the end point, so everything that goes up from 2, just needs to know if it can get to 2

This is the heart of the algorithm, if it can reach “dp[I]=1” and out of the inner loop, until the final result should look like this

“The 1 and 0 in the middle are not assigned because they don’t get to 2“

Finally, we determine whether “dp[0]==1” is true. If true, it means that we can start from 0 and reach the end point. It is clear that we are nearly “5 times” faster than the recursion

Optimal dynamic programming

We were thinking a little deeper, do we really need this array?

It doesn’t have to be, right? Why? Why do we need an array when we are always comparing to the “latest” element? This is very similar to LeetCode 53 – maximum suborder and – solution record (with dynamic programming) – GoLang. In other words, we can get rid of the array and simplify the code to something like this.

Func optimizeNonRecurrentJump(nums[] int) bool{aim := len(nums)-1; func optimizeNonRecurrentJump(nums[] int) bool{aim := len(nums)-1; i>=0; i-- { maxJump := min(i+nums[i], len(nums)-1) for j := i + 1; j<=maxJump; J ++{if j == aim{aim = I // update the nearest endpoint}}} if aim == 0{return true} return false}Copy the code

Create a new variable called AIM and always point to the last endpoint. If there is an element before it approaching the endpoint, update it. Finally, we determine if “AIM ==0” is true, and we know whether our first element can reach the endpoint

This plan is less expensive than the previous one“0.2 MB“The space has improved again.

Creation is not easy, I hope to leave your little zan zan, is the biggest encouragement

Other related topics link

LeetCode 55 – Jump Games – Solution Notes (Recursion + Dynamic programming) – Golang

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

LeetCode Code Collection – Continuously updated