Anxiety conversations,

First of all, I’m not selling anxiety. I’m selling anxiety. Secondly, I would like to thank my teacher, the most handsome west Lake…..

Anyway, in the comments section of leetCode you can see Lucifer, the Big Lucifer; His solution is in line with the thinking mode of human thinking, thinking point is very simple.

Why brush the algorithm? Because this is the big front-end era, and front-end development is actually a little bit easier than other areas, notice I didn’t say the front-end is easy, it’s relatively easy to get started. Simple to get started means that there will be a lot of people getting started. How do you stand out among the many primary front-end? I chose the brush algorithm, brush algorithm has the following advantages.

  1. This is true when it comes to business requirements that require algorithms.
  2. Can exercise their logical thinking, exercise internal skills.
  3. You can learn some new skills faster.

What exactly is dynamic programming

I know what you say and I can understand it. Why is it so easy to say/read and expensive to write?

Because most solutions, even in the Comments section of Leetcode, will only tell you the answer, not the way you think about it. Or some will tell you how to think, but they are experienced DP players, the way of thinking is not suitable for beginners, a dynamic transfer equation inexplicably comes out?? Black question marks. I’ve been there before. Thanks again, Big Lucifer.

How exactly do we learn dynamic programming? My advice is to bite the bullet and brush something simple, step by step, and then brush something difficult; Do not be impetuous in the process of brushing questions, do not just AC for AC’s sake, but through their own patient observation, abstraction, practice, induction and summary; Recurse until you understand DP and become familiar with DP. There really is no quick way, and if there is, it’s a lie. Here, combined with actual combat to take you over, with the way of thinking in line with human completely unpacked the pants of dynamic planning, learning dynamic planning.

If you’re not familiar with dynamic programming, or not at all, I suggest you take a look at my last article on dynamic programming.

53. Maximum suborder sum

All right, let’s go straight to the dish. Let’s look at the problem first;

            

What kind of problems are suitable for dynamic programming?

Don’t think too much about it. Let’s solve it by force in the simplest human way of thinking, and then consider the following two points based on the state tree.

So how violent is this? Nums [I] = nums[I] = nums[I] = nums[I] = nums[I] Do not look down on violence solution, is the breakthrough of DP!



Let’s look at the violent state tree, and I’ll just draw the first two longest branches, and you can imagine the rest.

       

Analyzing the two branches of the violence tree, it is clear that the answer is [4,-1,2,1]. The latter branch is -2 less than the previous branch, which means that the size of the problem is smaller, and the answer is still optimal, which means that there is an optimal substructure.

When we do the second branch, and we’ve already done the first branch, that’s the repeating subproblem.

In general, this maximum value type is more suitable for DP to solve; How to quickly use DP solution, it depends on your own to accumulate experience.

Defining states is the anchor of dynamic programming

Whether the state definition is correct or not directly determines whether your dp equation is correct or not, thus determining whether your dp mode is correct or not;

Before we define state, we need to be clear about two things, one is state, one is choice;

  • Nums [I] = nums[I] = nums[I]
  • Options: How many options are there for each state? [I] = nums[I] = nums[I] = nums[I]

Note: [state] and define state [is] two things, “state” is the title given conditions, conditions can affect the results, and define the definition state [is] in order to clarify the meaning of dp equation, so the according to the change of the state, using the mathematical induction for state transition equation, namely to find patterns.

For example, x + y = z, you have to know what your x, y, and z are in order to write a state transition equation like this;

Here, we define [state] and [choice], and define the state of the transition equation. We must be aware of two things.

  1. Subproblems (smaller problem size) to think about, to think about. So for this problem, let’s make the array smaller and smaller.
  2. What’s the last step, which is the last solution; (The last option used in optimal policy)

For example, nums = [-2,1,-3,4,-1,2,1,-5,4], what is the last step? What is the last choice used in the optimal strategy? Nums [6] = 1, nums[6] = 1, nums[6] = 1 If I choose 1, the answer is final [4,-1,2,1];

According to the above two points, combine two definite things, one is state and the other is choice.

  1. States: obviously nums[I], each number is a state
  2. State selection: For each state NUMs [I], we have two choices, either choiceNums [I], or not selected

At this point, the definition of state is pretty clear.

Dp [I] = x, indicating that the sum of the largest suborder ending with nums[I] is X; i < nums.length

State transition equation

You have to think about the definition of state, the definition of state directly determines whether your transfer equation is correct, whether your dp posture is correct;

Based on the above definition of states, let’s find the law (mathematical induction); Nums [I] is a state; For each state, we can choose, or not. If we choose nums[I], then the answer is nums[I] + dp[i-1]. If nums[I] is not selected, start with nums[I]. Enumerating all states, taking the maximum of the two choices, would be the answer, wouldn’t it? That’s the transition equation;

Dp [I] = Max (nums[I], dp[i-1] + nums[I]), I > 1

Initial conditions and boundaries

Because we are enumerating all the states, taking the maximum of the two choices is the answer, so the boundary is the array length; What is the initial value? Dp [I] = nums[I];

code

Make sure you understand the state definition, transition equation, boundary, and initial values before you start writing code. Think about it and write code very carefully.



152. Maximum subarray of product

Let’s do the same thing for the largest subarray of products



I’m not going to explain the violence solution, ditto;

The state is a nums[I], and for each NUMs [I] state, either select or not select two choices. But there’s an implicit condition to consider, which is multiplying two numbers:

  • If it’s a maximum (assuming a positive number) multiplied by a negative number, it’s a minimum
  • If the minimum (assuming a negative number) is multiplied by a negative number, it is the maximum

So when we enumerate all the states, according to these two conditions, constantly maintain the maximum and minimum value, encounter negative number is multiplied by the minimum value, encounter positive number is multiplied by the maximum value. It only depends on the maximum and minimum, so if we keep updating the enumeration state to get the answer, it’s the same thing if we’re dealing with 0;

Definition of state:

  • imin = min(min(nums[i] * imax, nums[i] * imin), nums[i]) 
  • imax = max(max(nums[i] * imax, nums[i] * temp), nums[i])


The initial condition is the first nums[I]

I’m just going to give you the code. QAQ



conclusion

I think DP is the best way to show the basic code skills, why? Because it’s hard.

Be sure to practice more, understand only I understand, you really understand must practice;

Also recommend a few articles and videos that I think are well written without advertising QAQ

Nine chapters dp video

Not a bad article

A very strong site B blogger