## 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.

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 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 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 π

1. State definition
2. List the state transition equation
3. 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 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 β­

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:

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:

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``

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 i-th 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 i-2
• So dp[I] = dp[i-1] + DP [i-2]

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 π β­ β­

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 anti-theft system, if two adjacent houses are broken into in the same night, the system will automatically alarm.

Given an array of non-negative 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``

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).

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 = 4-2 = 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 = 6-2 = 4. Then, by buying on day 5 (stock price = 0) and selling on day 6 (stock price = 3), the exchange makes a profit = 3-0 = 3.Copy the code``

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 non-owned 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 βοΈ

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