Finally come to this topic ~~~ Excited rubbing hands!

# 1. Basic knowledge

Dynamic Programming: Dynamic Programming (DP), if a problem has many overlapping sub-problems, experimental DP is the most effective

Therefore, as long as it is a question type that can be derived from the previous state, it can be used.

In dynamic programming, each state must be derived from the previous state. This distinguishes it from greed. Greed is not derived from the state, but directly selects the best locally.

Greedy cannot solve the problem of dynamic programming.

### 01. Huahua Explained

Requirements: The optimal sub-structure can be decomposed into sub-problems, and then recursively find the optimal solution of the sub-problem to obtain the optimal solution. Overlapping sub-problems Sub-problems overlap, so that we can only calculate once and store the solution for future use. Reduce time complexity (exponential to polynomial). If the sub-problems do not overlap -> Divide and Conquer has no aftereffects. When a sub-problem is When used to solve a larger problem, its optimal solution will not change

Top-down: Memoized recursion (from large to small)

Bottom-up :DP (from small to large)

Algorithm using DP:

Fibonacci sequence

LCS

Backpack

Freud

Washal Bellman

[The external link image transfer failed. The source site may have an anti-hotlinking mechanism. It is recommended to save the image and upload it directly ( img-n2gH09KX-1624203830729)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620125840171.png) ]

#### The first problem

[External link image transfer failed. The source site may have an anti-hotlink mechanism. It is recommended to save the image and upload it directly (img-UvlOTyaj-1624203830735)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images \image-20210620132135592.png)]

1. Prefix and[ The external link image transfer failed. The source site may have an anti-leech link mechanism. It is recommended to save the image and upload it directly (img-HuhNBM4v-1624203830741)( C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620132255046.png) ]

2. Climbing the stairs[The external link image transfer failed, the source site may be anti-theft Chain mechanism, it is recommended to save the picture and upload it directly (img-eUURX1j2-1624203830749)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620132304314.png) ]

[External link image transfer failed. The source site may have an anti-leech link mechanism. It is recommended to save the image and upload it directly (img-39bohMae-1624203830751) (C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620132542996.png) ]

3. Dajia Heshe[External link image transfer failed, the source site may have an anti-hotlink mechanism, it is recommended Save the picture and upload it directly (img-39lBWtQh-1624203830752)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620132324780.png) ]

[External link The image transfer failed. The source site may have an anti-hotlinking mechanism. It is recommended to save the image and upload it directly (img-24yGeDIr-1624203830754)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620132350512 .png) ]

4. The minimum number of exchanges to increase the sequence[The external link image transfer failed, the source site may have an anti-theft chain mechanism, it is recommended to save the image and upload it directly (img-RyI6Dj7s-1624203830755) (C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620132513639.png) ]

5. Domino and Tomino tiled[Failed to export images from external links , The source site may have an anti-leeching mechanism, it is recommended to save the picture and upload it directly (img-aRLCpSpE-1624203830758)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620132528137.png)]

#### Second problem

[External link image transfer failed. The origin site may have an anti-theft link mechanism. It is recommended to save the image and upload it directly (img-XCySdUVj-1624203830759)(C :\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620133111881.png) ]

[External link image transfer failed, the source site may have an anti-leech link mechanism, it is recommended to change Save the picture and upload it directly (img-Hh-1624203830760) (C:\Users\lh\AppDat a\Roaming\Typora\typora-user-images\image-20210620133121348.png) ]

1. Different path[External link image transfer failed, the source site may have anti-leeching mechanism, it is recommended to save the image Download and upload directly (img-dzmWUvfE-1624203830769)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210620133134412.png) ]

### ****** ************************************************** ************************************************** ***********************************

### 1, problem-solving steps

The state transition formula is very important, but DP is not only a recursive formula.

Five Steps of Dynamic Programming:

Determine the meaning of the dp array (dp table) and subscripts Determine the recursive formula How to initialize the dp array Determine the traversal order Example to derive the dp arrayNote: First Determining the formula, considering the initialization. Because in some cases, it is the recursive formula that determines how to initialize.

The 5 steps here must be clear to understand the whole process of DP~ Don’t just look atJust put it on the recurrence formula.

### 2. How should DP debug

The best way to find the problem is to print out the dp array and see if it is derived according to your own ideas! So pay attention to the dp array! ! !

When you encounter a problem, you can actually think about these three questions yourself:

Did I give an example to derive the state transition formula for this topic? Did I print the log of the dp array? Is the printed dp array the same as I thought?Be clear about where you don't understand:

Is it because the state transition does not understand, or the implementation code does not know how to write, or does not understand the order of traversing the dp array.### 3. DP main question type

Classic question knapsack problem, house robbery problem, stock problem sub-sequence problem[External link image transfer failed, the source site may have an anti-hotlink mechanism, it is recommended to save the image and upload it directly (img-j3-1624203830770)(C:\Users\lh\AppData\Roaming\Typora\typora-user-images\image-20210610184012519.png) ]

#### 3.1 Theories and principles of the backpack problem

Mainly master 01 backpacks and complete backpacks. At most one multi-pack is enough, and there is no problem with multi-packs.

strong> 1. Two-dimensional 01 backpackThere are N items, and a backpack that can carry a weight of W, the weight of the i-th item is weight[ i ], and the value obtained is value[ i] , Each item can only be used once to find out which items are packed into the backpack with the largest total value of items.

Example: Suppose the maximum weight of the backpack is 4, and the items are as shown in the table:

Solution 1: Brute force search, backtracking method

There are only two statuses for each item, take or not, use backtracking to search for all the situations, the time complexity is O (2^n), n represents the number of items

Solution 2: Dynamic programming

The optimization of the backtracking method.

Five Steps to Dynamic Programming:

1. Determine the meaning of the dp array and subscripts

dp[ i] [j] means from 0 to i subscripts Take any item from the item and put it in a backpack with a capacity of j. What is thethe largest sum of value. i corresponds to the item, which means to take any item from 0 to i, and j corresponds to the weight that the backpack can bear.

2. Determine the recurrence formula, that is, the state transition equation.

There are two directions to push Come out dp[ i] [j ], that is, for the i-th item, there are two states, whether to take or not, so there needs to be a judgment condition

If you don’t take:

Introduced by

dp[ i-1] [j ], the backpack capacity is j, and the maximum value of item i is not placed inside, that is, when the backpack’s capacity j is less than the weight of item i , at this time dp[ i] [j] is dp[ i-1] [j ]

If you take: by

dp[ i- 1] [j-weight[ i] ] is introduced,

that is, when the backpack’s capacity j is greater than or equal to the weight of item i, dp[ i-1] [j-weight[ i]] is the maximum value of item i when the backpack capacity is j-weight[ i ],

then

dp[ i-1] [j-weight[ i]] + value [i ] (the value of item i) is the maximum value of item i in the backpack.

So the recursive formula: dp[ i] [j] = max(dp[ i-1] [j ], dp[ i-1] [j-weight[ i]] + value[ i ]);

3. Initialization of dp array

Two directions, one is when i = 0, the other is when j = 0

For j = 0, initialize directly when initializing the dp array, because when the maximum weight of the backpack is 0, the value of the backpack can only be 0.

For i = 0, you need to use reverse traversal, use a for loop, and j traverse from back to front; because if you use positive traversal, item 0 will be added multiple times.

Note that this is easy to make mistakes. It must be traversed in reverse order to ensure that item 0 is only put in once. This is very important for 01 backpack. After initialization, the first row and the first column of the dp array are initialized.

For other arrays in the dp array, if there is no negative value in the title, you can directly initialize it to 0.

If a negative value appears, you need to initialize it to negative Infinite INT _ MIN

Attention: It is not necessary to add dp[ 0] [j-weight[ 0]] during initialization, even if only value[ 0] is available, but it is added for the purpose of scrolling the array Echoing writing style.

4. Determine the traversal order. There are two dimensions in the traversal of this question: one is the item and the other is the weight of the backpack. You need to consider who to traverse first. It turns out that traversing the items first is easier to understand. Then understand, why are both directions possible? To understand the nature of recursion and the direction of recursion. It can be seen from the recursive formula that dp[ i] [j] is derived from dp[ i-1] [j] and dp[ i-1] [j-weight[ i] ]. dp[ i-1] [j] and dp[ i-1] [j-weight[ i]] are both in the positive left and positive directions of dp[ i] [j ], then go straight up first, or It's the same if you go straight to the right first. // The first one traverses the items first, and then traverses the weight of the backpack // The size of the weight array is the number of items for(int i = 1; iLabel group:[Array] [dynamic programming] [initialization] [Array formula] [Traverse] [typora] [Knapsack problem dynamic programming] [Knapsack problem] [Anti-leech]