Article From:

Just nibbling all afternoon and DP for a night, I feel a little bit of practice, but practice is not enough.

Let me briefly summarize my understanding of DP.

What is DP?

Compression dp== state compression +dp

State compression

We often encounter a problem with many states, not only complex situations, many states, there are many restrictions.

In this way, it is difficult to run through time.

In this case, we need to compress a large number of states into a number, most commonly binary state compression

For example, 0 is usually used for empty, and 1 for occupancy.

If you have a row of eight lattices, you can use the binary number of eight to indicate whether each lattice is occupied, and we only need to store the corresponding decimal number in the array, traversal can also be directly traversed to this state.


dpSimilarly, to satisfy the subproblem’s optimality and no aftereffect, there is also a DP equation to be written, but the DP definition and the state transition equation of the entrance-level difficulty of the symmetric DP are more routine.

1、If the current line has an effect on the top T line, we define DP [i] [j] [k]…………………… [z] for line i, the current line selection state j, and the I-1 line selection state……….. I-T + 2 line state is the answer to Z.It is used to represent the first few rows, and generally affects two rows and three rows.

2、Transfer equation.

Find the solution number (here we take three-dimensional example): DP [i] [j] [k] + = DP [i-1] [k] [s] (both K and s need enumeration), and output the answer: DP [n] [i] [j] (enumeration row n)

Find the most value: dp[i][j][k]=max{dp[i-1][k][s]}. Output answer: Max (dp[n][i][j])

3、We need to pre process the answers to the previous t row.

Preparatory knowledge (routines)

This part can be skipped without looking.

The following part of the comparison two, because the bitwise operation of this thing to understand the people see through, do not understand only rely on output to see, miserable, gnaw very slowly, I belong to the latter, so I wrote a little more detailed.

1、Basically left and right shift: x< < K, X shifted to K position. X> > K, X shifted to K position. (generally used to initialize binary maps to determine whether the state of the same row is clash).

2、Binary map mp[i]= (mp[i]< < 1) +e[i][j]. is equivalent to storing the location of each row to support placement. Move to the left = = give up a vacancy to give the new lattice.

3、Full state: (assuming a row has m lattices) (1 & lt; & lt; m) – 1, for example, when m = 3, the three left shifts to 1000, and – 1 turns to 111, becoming exactly the state in which all three lattices are selected

4、(iFor the current state of enumeration (i & lt; & lt; 1) & amp; I determines whether the row I satisfies both adjacent and non-adjacent grids. Why can we judge I by moving it ourselves? For example, I = 0110, left shift to 11001100 and 0.110 is 1 in the third place (equal to the third and second digits of the prime number are 1), so this state is illegal.

Similarly, (i< < 2) & I, can it be judged whether every two lattices are selected?

5、 j & mp[i] ==j It is used to determine whether line I of the original map supports the state of J. Similarly, K & amp; J can determine whether the two states of K and J conflict.

Introductory topic

First, familiarize yourself with templates.

Then do a little variation.

Finally, learn about the idea of reduced state and the processing of higher dimensional DP.


Link of this Article: [summary] DP

Leave a Reply

Your email address will not be published. Required fields are marked *