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 frontend 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 use
The historical record
So 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 subproblems to solve, which is also expected by dynamic programming.
So here is just an example, the followup 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[i1] and DP [i2].
For example, in the following problem of climbing the ladder, the state transition equation π
dp[i] = dp[i1] + dp[i2]
Copy the code
 First, dp[I] represents the number of schemes to the ith ladder
 So to climb the ith ladder, there are two situations π
 Climb one more step from i1 to i1
 Step I2 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 n2nd item, or the n3rd item.
 At this point, we need to initialize the value of the DP array, in general, for example
dp[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.
A few questions are recommended here π
 Partition and subsets – 01 knapsack
 Target and 01 knapsack – number of options
 Change exchange – complete backpack
 Change exchange – II (full backpack – Number of options)
 One and zero – (2d cost backpack)
Linear dp
 As the name suggests, linear DP is DP on a line.
 Or the way I understand it, it’s just recursion over linear space.
A few questions are recommended here π

Longest ascending subsequence

Minimum path sum of triangles

Longest common subsequence

Maximum suborder sum

The Russian doll envelope problem
Interval dp

As the name implies, in a segment of dp, similar to DP [L][r], we also break the big problem into small problems to deal with, here is broken into small cells to deal with.

Then after processing the intercell, and then backtracking to find the value of the large interval.

There are two main methods, mnemonic search and recursion.
A few questions are recommended here π
 Longest echo subsequence
 Statistical subsequence of different echo
 Lowest score for polygonal triangulation
 Poke the balloon
 Weird printer
The tree dp
 To be precise, the tree DP is exactly the idea of DP, based on the tree structure.
 You can think of it as, you define the DP equation in a tree, and you do it accordingly.
A few questions are recommended here π
 Robbery III
 Temporal synchronization
 Course selection
 The maximum sum of paths in a binary tree
 The diameter of the binary tree
 Strategy game
Digital dp
 Digit DP is a kind of counting DP, which is generally to count the number of conditions in an interval [LE,ri].
 By digitaldp, it literally means doing digitalDP.
 Digit is also a more pleasant name, the meaning of digit: a number has one place, ten place, hundreds place, thousands place…… Each digit of a number is a digit!
A few questions are recommended here π
 The number of 1s
 Combination of numbers with a maximum value of N
 Smallest integer divisible by K
In my impression, this is a template, it is difficult to write by yourself, but this is a board topic, ha ha ha, hit Acm all know, here is not expanded.
State compression, DP, counting, DP, recursion, DP, probability, DP, game, yeah, that’s a lot, just to get some ideas.
Three examples
Next, let’s use three examples to reinforce the three steps of our solution π
Climb the stairs β
Links: Climb the stairs
Suppose you are climbing the stairs. It takes you n steps to get to the top.
You can climb one or two steps at a time. How many different ways can you climb to the top of the building?
Note: ** given n is a positive integer.
Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 2. 2Copy the code
Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building. 1. 1 + 1 + 1 2. 2 + 1 3Copy the code
Source: LeetCode link: leetcodecn.com/problems/cl… Copyright belongs to collar network. Commercial reprint please contact the official authorization, noncommercial reprint please indicate the source.
Let’s go through π
Step 1: State definition
Dp [I] indicates the number of schemes up to order I
Step 2: Determine the state transition equation
According to the actual situation, we can easily think of π
 There are two ways to get to the ith ladder
 In the first case, you just take a step up from I minus one
 In the second one, I take two steps up from i2
 So dp[I] = dp[i1] + DP [i2]
Step three, initialize the state, dp array
dp[1] = 1,dp[2] = 2
Copy the code
By following these three steps, we can write the complete solution code
Code π
The code can be found here at βοΈ
Playing house rob π β β
Link: Home Robbery II
You are a professional thief, planning to steal houses along the street, each with a certain amount of cash hidden in it. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with a connected antitheft system, if two adjacent houses are broken into in the same night, the system will automatically alarm.
Given an array of nonnegative integers representing the amount of money stored in each house, calculate the maximum amount you can steal without activating the alarm.
Example 1:
Input: [2,3,2] Output: 3 Explanation: You cannot steal house 1 (amount = 2) and then house 3 (amount = 2) because they are adjacent.Copy the code
Example 2:
Input: [1,2,3,1] Output: 4 Explanation: You can steal house 1 (amount = 1) and then steal house 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4.Copy the code
Source: LeetCode link: leetcodecn.com/problems/ho… Copyright belongs to collar network. Commercial reprint please contact the official authorization, noncommercial reprint please indicate the source.
Let’s go through π
Step 1: State definition
// dp[I][0] = (1) dp[I][0] = (1Copy the code
Step 2: Determine the state transition equation
/ / the first room I steal, dp [I] [1] = nums [I] + dp [0] [I  1] / / the first room I don't steal, dp [I] [0] = math.h Max (dp [0], [I  1] dp [I  1] [1])Copy the code
Step three, initialize the state, dp array
// dp[0][0] = 0
// dp[0][1] = nums[0]
Copy the code
But the difficulty of this subject lies in π
The first house is next to the last house, which means that we need to make some changes, which I also did at the prompt, cleverly written, let’s take a look at the code π
By following these three steps, we can write the complete solution code π
The code can be found here at βοΈ
The best time to buy and sell stocks IVβββ
Given a binary tree, you are asked to return the values of the nodes it traverses sequentially. (that is, access all nodes layer by layer, from left to right).
Link: The best time to Buy and Sell stocks IV
Given an array, the ith element is the ith day price of a given stock.
Design an algorithm to calculate the maximum profit you can make. You can complete up to K transactions.
Note: You cannot participate in more than one trade at a time (you must sell your shares before buying again).
Example 1:
Input: [2,4,1], k = 2 Output: 2 Explanation: If you buy on day 1 (stock price = 2) and sell on day 2 (stock price = 4), the exchange will make a profit = 42 = 2.Copy the code
Example 2:
Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (stock price = 2), sell on day 3 (stock price = 6), this exchange will make a profit = 62 = 4. Then, by buying on day 5 (stock price = 0) and selling on day 6 (stock price = 3), the exchange makes a profit = 30 = 3.Copy the code
Source: LeetCode link: leetcodecn.com/problems/be… Copyright belongs to collar network. Commercial reprint please contact the official authorization, noncommercial reprint please indicate the source.
Step 1: State definition
// dp[I][j][0] represents the cumulative maximum profit after selling on day I. // DP [I][j][1] represents the cumulative maximum profit after buying on day I. // Dp [I][j][1] represents the cumulative maximum profit after buying on day ICopy the code
Step 2: Determine the state transition equation
// Step 2: // dp[I][J][0] We need to determine whether to hold shares yesterday / / dp [I] [j] [0] = Max (dp [I  1) [j] [0], Dp [I  1) [j] [1] + prices) / / dp [I] [I] [j] [1] the first day, I also we need to determine whether to hold shares yesterday / / dp [I] [j] [1] = Max (dp [I  1) [j] [1], dp[i  1][j  1][0]  prices[i])Copy the code
Step three, initialize the state, dp array
// All nonowned status values are initialized to 0. The status of all holdings is set to a large negative value (at least 1 minus the largest share price), indicating unknown. // dp[0][j][0] = 0; // dp[0][j][1] = prices[i];Copy the code
But the difficulty of this subject lies in π
When k is greater than len over 2, we need to do a process, or we need to use state compression. That’s hard. Let’s see how we can write π
The code can be found here at βοΈ
Summary of advanced questions
Here are some of the topics I collected. I hope they will be helpful to you.
simple
 Climb the stairs
 Al shabaab
 Use minimal cost to climb stairs
 Continuous sequence
 Three problems
medium
 Robbery II
 The best time to buy and sell stocks includes the cold period
 Robbery III
 Different paths
 Different Paths II
 Longest ascending subsequence
difficult
 The best time to buy and sell stocks III
 The best time to buy and sell stocks
 The frog crossing the river
 Word Split II
 Maximum submatrix
reference
 Say goodbye to dynamic programming, even brush 40 questions, I summarized these routines
 How to understand dynamic programming?
 Knapsack problem series for dynamic programming
 Nine Stories of backpack by DD Daniel
 [force buckle] DP problem classification summary
β€οΈ Thank you all
If you found this helpful:
 Like support, let more people can also see this content.
 Pay attention to the public number frontend UpUp, contact the author, we learn together progress.
 If you like it, you can also read TianTian’s recent article (thanks to the encouragement and support from friends of Mine πΉπΉπΉ) :
 “Once and for all” A brain map to master Git commands (1340+π)
 “Once and for all” 48 photos to show you the beauty of Flex layout (800+π)
 My 2020 front interview secrets, for your autumn recruit escort (490+π)
 “Noodles” Three rounds of netease Noodles you may need (340+π)
 “Once and for all” WebPack4 configuration (960+π)
 “Fill in the Gaps” to strengthen your HTTP knowledge (1050+π)
 Here are 21 highly frequent JavaScript handwritten interview questions for you once and for all (666+π)
 18 browser interview questions (820+π)
 54 JavaScript interview questions (670+π)