"Algorithms and Data Structures" a brain map shows the beauty of dynamic programming algorithms

preface

There is a special topic in the algorithm, dynamic programming, which is very important, and it was more or less involved in the interview of Daco. Before COMING to netease, I brush part of DP, and this time I just comb it again, I hope it will be a little helpful to you.

If you already understand the idea of DP, or if you already know the common dp solution, you can skip it.

If you don’t know about dynamic programming, or know about dynamic programming, but haven’t started brushing up yet, maybe this article is for you.

Public number front-end UpUp, reply DP, you can get the brain map.

Contact 👉TianTianUp, if you encounter problems, you can contact the author oh, willing to accompany you to study together to discuss the problem.

Brain figure 👇

What is dynamic programming

For this reason, it is often used to refer to Dynamic Programming. Dynamic programming, first of all, what is it, what does it solve, what does Wikipedia say about it 👇

Dynamic programming is effective in finding the best solution for cases where there are many overlapping subproblems. It reorganizes problems into subproblems, and in order to avoid solving these subproblems multiple times, their results are gradually computed and stored, from simple problems until the entire problem is solved. Therefore, dynamic programming stores the result when recursively, and therefore does not spend time solving the same problem.

Dynamic programming can only be applied to problems with optimal substructures. Optimal substructure means that the local best solution determines the global best solution (for some problems this requirement is not completely satisfied, so some approximations may be introduced). Simply put, a problem can be broken down into subproblems to solve.

Let me summarize a little bit 👇

Breaking a big problem down into subproblems is called a substructure.
Each optimal solution, the optimal value, is derived from [these small subproblems].
It’s more important to useThe historical recordSo we don’t have to double count.

What is double counting, and how can we use history to reduce unnecessary computation 👇

Let’s take the Fibonacci problem to 👇

If we were to write this recursion, it would go as follows: 👇

It computes the result many times, the point that fits the dynamic programming, ** Dynamic programming is effective in finding the best solution for cases where there are many overlapping subproblems. ** And for this problem, it can continue to be broken down into smaller sub-problems to solve, which is also expected by dynamic programming.

So here is just an example, the follow-up will do the train of thought 👇

Dynamic programming problem solving in three steps

For beginners, it takes a short time to master, I think it is very difficult, so HERE I recommend you can look at the classic dynamic programming 👉 backpack nine, click here, read it, may be a little help to you.

Solution idea, three steps 👇

State definition
List the state transition equation
Initialization state

State definition

We need to use an array to hold the results of the previous calculation, so we usually use an array to maintain our results, usually dp array.
The meaning of the dp array must be clear, that is, the meaning of the dp[I] expression, for example, dp[I] expression of the number of schemes to reach the ith ladder.

List the state transition equation

In plain English, finding the relationships between arrays is the most difficult and most important step in solving the dynamic specification problem.
Generally speaking, the transition equation of DP [I] states has some relation with dp[i-1] and DP [i-2].

For example, in the following problem of climbing the ladder, the state transition equation 👇

dp[i] = dp[i-1] + dp[i-2]
Copy the code

First, dp[I] represents the number of schemes to the ith ladder
So to climb the i-th ladder, there are two situations 👇
- Climb one more step from i-1 to i-1
- Step I-2 and climb two more steps to step I
So its equation of state transition is going to be this one up here

Initialization state

What we’ll find is that the NTH item in our DP array is determined by solving the state transition equation, so what we need is the NTH item, or the n-2nd item, or the n-3rd item.
At this point, we need to initialize the value of the DP array, in general, for exampledp[1],dp[2].dp[1][1].dp[1][2].

From the above scenario, climb the stairs, we need to start the DP array, when we iterate to dp[3] = dp[1] + dp[2], then we do not need to decompose.

At this point, we’re actually going to need to initialize the dp[1] and dp[2] arrays.

Dynamic programming classification

For a long time, with the idea of dynamic programming algorithm by a lot of people to explore, dynamic programming, this kind of problem, is divided into many kinds, refer to the information on the Internet, listed a few common DP, let’s look at it next.

My experience talk, according to different DP special topics to brush, the effect is very obvious, of course, specific to see yourself to master the situation, and brush the problem speed.

Backpack dp

This is a more classic topic in state planning, for understanding DP, I personally feel very helpful, but also my introduction to DP at the beginning of the topic 👇

Dd Daniel’s “backpack nine tell” 👈, you can see this, here is not expanded.