Chapter on Dynamic Programming (DP)

I’m going to talk about it from two perspectives

  1. Common DP models
    • Knapsack problem
  2. Different types of DP
    • Linear DP
    • Interval DP
    • State compression DP
    • The tree DP
    • Counting class DP
    • Digital statistics DP

Dynamic planning has no code template, it is more mathematical, its core part lies in the state representation and state transfer.

There are 3 sections in total. The first section is expected to cover the backpack problem.

Dynamic Programming (I)

What is the backpack problem?

The essence of the backpack problem is that given a pile of items and a backpack, each item has two attributes of volume and value. Under some restrictions, some items can be loaded into the backpack, so that the maximum value can be obtained under the condition of not exceeding the volume of the backpack. According to different restrictions, can be divided into different types of backpack problems.

0-1 knapsack

Given NNN items and a backpack with a capacity of VVV, each item has two attributes, viv_IVI (V for volume) and wiw_iwi (W for weight), each item can only be used once (0-1 backpack features, Each item can be used either 1 time (put into the backpack) or 0 times (do not put into the backpack). What items can be put into the backpack so that the total volume of items does not exceed the capacity of the backpack, and the total value is the maximum.

DP problems are usually considered from two aspects: state representation and state calculation

  • State said

    Consider from two aspects

    • Set (what kind of set a particular state represents)
    • Property (what property of the collection this state holds)
      • Maximum value of set
      • The minimum value of the set
      • The number of elements in the set

  • State calculation

    State transition equation. The partition of sets. For example, if I (I,j)f(I,j)f(I,j)f(I,j)f(I,j), consider how to divide it into smaller subsets, and these smaller subsets, in turn, can be divided into smaller subsets.

    There are two principles for the division of sets:

    • Not heavy: that is, without repetition, an element cannot be A member of both subsets A and B
    • Not leaky: that is, no element is omitted, and an element cannot belong to any subset.

    The principle of no leakage usually needs to be met, but not heavy.

For example, for the 01 backpack, the state f(I,j)f(I,j)f(I,j) represents the set of all options (which items to choose). And iii, JJJ means: select only from the previous iii items, JJJ means that the total volume selected is less than or equal to JJJ. F (I,j)f(I,j) the value of f(I,j) is the maximum total value.

That is, f(I,j)f(I,j)f(I,j)f(I,j) is the maximum total value that can be selected only from the previous iii items, and the total volume of the selected items is less than or equal to JJJ.

01 Backpack final answer should be F (N,V) F (N,V)f(N,V)f(N,V), i.e., the maximum value that can be obtained from the previous NNN items whose total volume does not exceed VVV.

Now consider the calculation of the state. For F (I,j) F (I,j) F (I,j) is divided into two categories, one is the selection method that does not contain the third item, the other is the selection method that contains the third item.

So, on the left side of the selected method is the maximum value of f (I – 1, j) f (I – 1, j) f (I – 1, j), the right to choose law is the maximum value of f (I – 1, j – vi) + wif (I – 1, j – v_i) + w_if (I – 1, j – vi) + wi. F (I, j) f (I, j) f (I, j) final values, is the one, left and right sides of the larger namely


f ( i . j ) = m a x { f ( i – 1 . j ) . f ( i – 1 . j – v i ) + w i } f(i,j)=max\{f(i-1,j),f(i-1,j-v_i)+w_i\}

Practice: Acwing-201 backpack problem

Naive approach (use a two-dimensional array to represent the state, note that the right set may not exist, when j

#include <iostream>

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main(a) {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			f[i][j] = f[i - 1][j];
			if(j >= v[i]) f[i][j] = std::max(f[i][j], f[i - 1][j - v[i]] + w[i]); }}printf("%d", f[n][m]);
}
Copy the code

To optimize the

Instead of using a two-dimensional array to represent states, you can use a one-dimensional array, using a scrolling array. Note: Optimization of dynamic programming is usually equivalent to the code or state transition equation.

#include <iostream>

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main(a) {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= n; i++) {
		for(int j =m; j >= v[i]; j--) {
			f[j] = std::max(f[j], f[j - v[i]] + w[i]); }}printf("%d", f[m]);
}
Copy the code

Optimizing with a one-dimensional array is a bit confusing at first, but you can print out the state transition process in the middle to make it easier to understand. Since f(I,j)f(I,j)f(I −1,j) depends on f(I −1,j)f(i-1,j)f(I −1,j) when calculating f(I,j)f(I −1,j), therefore, at the level of iii, enumerations must start from 111 to NNN, and FFF with a lower level of III must be calculated first before the following can be iterated. So the enumeration of III cannot be reversed.

However, we find that for outer loop III, FFF of layer I − 1i-1I −1 will be used in each loop, so one-dimensional array can be used for optimization. Since FFF of smaller JJJ needs to be used to update FFF of larger JJJ during update, If the JJJ also raised to iterate the update f (j) f (j) f (j), using the f (j – v [I]) f (j – v [I]) f (j – v [I]), because of the j – v [I] [I] < < jj – v jj – v [I] < j, F (j – v [I]) f (j – v [I]) f (j – v [I]) must be ahead of f (j) f (j) f (j). When update f (j) f (j) of f (j) f (j – v [I]) f (j – v [I]) f (j – v [I]), in fact is the updated value, namely f (I) (j – v [I]) f (I) (j – v [I]) f (I) (j – v [I]). So we enumerate JJJ in reverse order, from large to small, to ensure that f(j−v[I])f(j−v[I])f(j−v[I]) has not been updated when f(j)f(j)f(j) f(j-v[I])f(j−v[I]) has not been updated. Its still on a round of f (j – v [I]) f (j – v [I]) f (j – v [I]), namely it is f (I – 1, j – v [I]) f (I – 1, j – v [I]) f (I – 1, j – v [I])

Examples are as follows: suppose N=4N =4N =4, V=5V =5V =5, for I =0i =0i =0, FFF are all 0. The volume and value of the items are:

V1 = 1V_1 = 1V1 =1, v2=2v_2= 2V2 =2, V3 = 3V_3 = 3V3 =3, V4 = 4V_4 = 4V4 =4

W1 = 2W_1 = 2W1 =2, W2 = 4W_2 = 4W2 =4, W3 = 4W_3 = 4W3 =4, W4 = 5W_4 = 5W4 =5

GIF illustration:

Since each round of calculation only depends on the FFF of the previous row, the idea of rolling array can be used to store FFF with a one-dimensional array. Since f(j)f(j)f(j) f(j) depends on f(j−v[I])f(j−v[I])f(j−v[I])f(j−v[I]) when enumerating JJJ, From big to small, to ensure that f (j) f (j) f (j) update, predated f (j – v [I]) f (j – v [I]) f (j – v [I]), to ensure that round is used f (j – v [I]) f (j – v [I]) f (j – v [I]) to update the f (j) f (j) f (j).

Completely backpack

The definition is similar to 0-1 knapsack, except that each item can be used an unlimited number of times

Recall that there are two ways to think about dynamic programming: state representation and state computation.

Status: Same as 01 knapsack.

State calculation: different from 01 backpack. 01 Backpacks are divided into 2 categories according to item III. Complete backpacks can be divided into groups according to the number of items selected by the third item. For example, the 0th subset means zero items for the third item, the 1st subset means one item for the third item, and the 2nd subset means two items,…. , the NTH subset means to select n (assuming that at most n can be selected, otherwise there is not enough knapsack capacity).

Then its state transition equation is:

F (I, j) = Max {f (I – 1, j – k * v [I]) x w + k [I]} f (I, j) = Max \ {f (I – 1, j, k \ times v [I]) + k \ [I] times w \} f (I, j) = Max {f (I – 1, j – k * v [I]) x w + k} [I], in which k ∈ k \ [0, n] in [0, n] k ∈ (0, n)

Practice: ACwing-3. Complete backpack problem

Write a naive version of the moving gauge as described above

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX][MAX];

int v[MAX], w[MAX];

int main(a) {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= V; j++) {
			for(int k = 0; j >= k * v[i]; k++)
			    f[i][j] = std::max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); }}printf("%d", f[N][V]);
}
Copy the code

After submitting, we found that TLE timed out, so we thought about how to optimize.

According to the derivation above, we can actually derive f(I,j)f(I,j)f(I,j) from two states, F (I, j) = Max {f (I – 1, j), f (I, j – v) + w} f (I, j) = Max \ {f (I – 1, j), f (I, j – v) + w \} f (I, j) = Max {f (I – 1, j), f (I, j – v) + w}, So f(I,j)f(I,j)f(I,j) has nothing to do with KKK. So based on this state transition equation, we write the following code

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX][MAX];

int v[MAX], w[MAX];

int main(a) {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= V; j++) {
		    f[i][j] = f[i - 1][j];
			if(j >= v[i]) f[i][j] = std::max(f[i][j], f[i][j - v[i]] + w[i]); }}printf("%d", f[N][V]);
}
Copy the code

This time the submission is AC.

Then we observe that a two-dimensional array can still be optimized into a one-dimensional array using the idea of scrolling arrays, as follows:

F (I,j) depends on f(I,j−v[I]), f(I,j) depends on f(I,j−v[I]), depends on the line, not the previous line, so the enumeration of JJJ is increased from small to large, Ensure the update f (I, j) f (I, j) f (I, j), f (I, j – v [I]) f (I, j – v [I]) f (I, j – v [I]) has been updated)

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX];

int v[MAX], w[MAX];

int main(a) {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = v[i]; j <= V; j++) {
			f[j] = std::max(f[j], f[j - v[i]] + w[i]); }}printf("%d", f[V]);
}
Copy the code

It can be found that the state transfer equations of the complete backpack and 01 backpack are very similar

01 knapsack: F (I, j) = Max {f (I – 1, j), f (I – 1, j – v [I]) + w [I]} f (I, j) = Max \ {f (I – 1, j), f (I – 1, j – v [I]) + W \ [I]} f (I, j) = Max {f (I – 1, j), f (I – 1, j – v [I]) + w} [I]

Full backpack: F (I, j) = Max {f (I – 1, j), f (I, j – v [I]) + w [I]} f (I, j) = Max \ {f (I – 1, j), f (I, j – v [I]) + w \ [I]} f (I, j) = Max {f (I – 1, j), f (I, j – v [I]) + w} [I]

When I do one-dimensional array optimization, Because of 01 knapsack f (I, j) f (I, j) f (I, j) is dependent on a line (I – I – I – 1 1 1) state (i.e., f (I – 1, j – v [I]) f (I – 1, j – v [I]) f (I – 1, j – v [I])), so make sure to update the f (j) f (j) f (j), F (j – v [I]) f (j – v [I]) f (j – v [I]) is still on the line of value, namely the f (j) f (j) f (j) to update, f (j – v [I]) f (j – v [I]) f (j – v [I]) after the update, so JJJ enumeration from big to small.

And backpack entirely, to the contrary, f (I, j) f (I, j) f (I, j) is dependent on the state of the bank (i.e., f (I, j – v [I]) f (I, j – v [I]) f (I, j – v [I])), so make sure the update f (j) f (j) f (j), F (j−v[I])f(j-v[I])f(j−v[I])f(j−v[I]) has been updated, so JJJ’s enumeration is going from small to large.

Multiple backpack

The number of items per item is different, for example, the number of items per item is sis_isi.

The state transition equation for multiple backpacks, as for full backpacks, is as follows

F (I, j) = Max {f (I – 1, j – v [I] * k) + k * v [I]} f (I, j) = Max \ {f (I – 1, j – v [I] \ times k) + k \ times V [I] \} f (I, j) = Max {f (I – 1, j – v [I] * k) + k * v [I]}, k ∈ \ [0, [I]] s k in [0, [I]] s k ∈ [0, [I]] s

Multiple backpacks just add a number limit to each item, while full backpacks have no number limit.

Practice: ACwing-4. Multiple knapsack problem I

Simple version of the problem:

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX][MAX];

int v[MAX], w[MAX], s[MAX];

int main(a) {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d%d", &v[i], &w[i], &s[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= V; j++) {
			for(int k = 0; j >= k * v[i] && k <= s[i]; k++)
			    f[i][j] = std::max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); }}printf("%d", f[N][V]);
}
Copy the code

Plain version of the code, and complete backpack almost exactly the same, but the inner loop more than a k≤ S [I]k \le s[I] K ≤ S [I] condition, try to submit AC. This is because the range of N is relatively small, the maximum is only 100, while the time complexity of naive method is O(n3)O(N ^3)O(n3), so the maximum time complexity is 10810^8108. Multiple knapsack problem II

Now let’s think about how do we optimize

First of all, according to the optimization idea of complete knapsack, the state transition equation is derived :(v represents v[I], w represents w[I], s represents s[I])

f[i,j] = max(f[i-1,j], f[i-1,j-v] + w, f[i-1,j-2v] + 2w ,... , f[i-1,j-sv] + sw) f[i,j-v] = max( f[i-1,j-v], f[i-1,j-2v] + w ,... , f[i-1,j-sv] + (s-1)w + f[i-1,j-(s+1)v] + sw)Copy the code

As you can see, the two state transition equations, only the middle part is the same, can’t be replaced.

Binary optimization

Consider a binary approach, such as for an I whose s[I]=1023, then enumerate 0,1,2,3,…. for that item ,1023, a total of 1024 cases. We can do this: just keep powers of 2, and then use powers of 2 for the rest of the numbers.

For example, for 0 to 1023, we only keep 1,2,4,8,16… 512 there are 10 digits in total. Any number from 0 to 1023 can be obtained by adding the 10 digits together. (The essence of the idea is to convert a decimal number into a binary representation.) So instead of enumerating 0 through 1023, we just need to enumerate 1,2,4,8… 512 is just 10 numbers.

If s[I] is not a power of 2, it is not a power of 2. For example, if s[I]=200, we need 1,2,4,8,16,32,64. We can’t ask for 128, because when we add 128, the range of numbers we can get is more than 200, and the maximum number we can get from 1,2,4,8,16,32,64 is 127, which is 73 away from 200, so we add 73, So we can use 1,2,4,8,16,32,64,73 to make up any number between 0 and 200.

How do you prove that you can use these numbers to get any number between 0 and 200?

First of all, 1,2,4,8,16,32,64 makes zero to 127, that’s indisputable. And any combination from 0 to 127, plus an extra 73, will make 73 to 200, so the eight numbers above will make any number from 0 to 200.

Logs [I]log_{s[I]} log_{s[I]}logs[I]. Then for these new items, do the 01 backpack problem once.

#include <iostream>

// Because there are N=1000 items, and the maximum s[I] of each item is 2000, so each item can be split into log(2000)≈11, which is actually less than 11.
// So the total number of items after splitting is not more than 1000 * 11 = 11000, so we can turn N to 11000
const int N = 11000;

int n, m;

int v[N], w[N], f[N];

int main(a) {
	scanf("%d%d", &n, &m);
	int cnt = 0;

	for(int i = 1; i <= n; i++) {
        // Process input, split s[I] items into log(s[I]) items
		int a, b, s;
		scanf("%d%d%d", &a, &b, &s);
		int k = 1;
		while(k <= s) {
			cnt++;
			v[cnt] = a * k;
			w[cnt] = b * k;
			s -= k;
			k *= 2;
		}
		if(s > 0) {
			cnt++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}

	n = cnt; // How many new items are split into

    // For the new item, do the 01 knapsack problem, here directly write a one-dimensional array optimized 01 knapsack
	for(int i = 1; i <= n; i++) {
		for(int j = m; j >= v[i]; j--) {
			f[j] = std::max(f[j], f[j - v[i]] + w[i]); }}printf("%d", f[m]);
}
Copy the code

Packet backpack

There are NNN groups of items, with several items in each group and at most one item selected from each group.

The grouping knapsack problem is thought of in a similar way to the previous one. The difference is only in state transitions.

01 knapsack state transfer, is enumerating the I item selected or not selected;

Full knapsack and multiple knapsack are the i-th item in the enumeration, select 0,1,2,3,4,…. a

And grouping knapsack, the enumeration is the ith grouping, which one to select, or not to select

The state transition equation of grouping knapsack is:

F (I, j) = Max {f (I – 1, j), f (I – 1, j – v [I, k]) + w (I, k} f (I, j) = Max \ {f (I – 1, j), F (I – 1, j – v [I, k]) + w (I, k \} f (I, j) = Max {f (I – 1, j), f (I – 1, j – v [I, k]) + w (I, k}, k ∈ \ [1, s [I]] k in [1, s [I]] k ∈ [1, s [I]]

Where V [I,k]v[I,k]v[I,k] represents the volume of KKK item in group III, w[I,k]w[I,k] W [I,k]w[I,k] similarly

Practice: ACwing-9. Group backpack problem

#include <iostream>

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main(a) {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &s[i]);
		for(int j = 0; j < s[i]; j++) {
			scanf("%d%d", &v[i][j], &w[i][j]); }}for(int i = 1; i <= n; i++) {
		for(int j = m; j >= 0; j--) {
			for(int k = 0; k < s[i]; k++) {
				if(v[i][k] <= j) {
					f[j] = std::max(f[j], f[j - v[i][k]] + w[i][k]); }}}}printf("%d", f[m]);
}
Copy the code