DP - Red Huang

Dynamic Programming Classic Tutorial
Introduction: After solving some problems, I have some thoughts on DP, so I wrote this summary:
Section 1 Basic Concepts of Dynamic Programming

The three elements of dynamic programming: stages, states, decisions.
Their concepts are everywhere, so I won't elaborate much. I will only share my understanding of them:
If we consider the process of solving dynamic programming as a production line in a factory, the stage is the different links in producing a certain product, the state is the current form of the workpiece, and the decision is the operation on the workpiece. Clearly, different stages summarize the various states of the product, and each small summary forms the final entire production line. There are also associations between each state (the next state is generated after a certain decision is made from the previous state).
Here’s an example:
To produce a batch of ice cream, there are many links in this process: buying milk, purifying the milk, processing it in the factory, packaging the processed product, and then selling it... Each link can be seen as a stage; the product has different states at different times. At the beginning, it is just white milk, after entering production, it takes various shapes, and after being taken out of the freezer, it becomes ice cream (from liquid to solid =_=||). Each form is a state, and the operation of freezing is a decision that changes the state from liquid to solid.
A state becomes another state after a decision, and this process is called state transition. The equation used to describe state transitions is called the state transition equation.
After this example, I believe everyone has some understanding of dynamic programming.
Next, I will discuss another understanding of dynamic programming:
Understanding dynamic programming with graph theory knowledge: Abstract the states in dynamic programming into points, and connect directly related states with a directed edge. The cost of state transition is the weight on the edge. This forms a directed acyclic graph (DAG) (Why acyclic? Read on). Performing a topological sort on this graph, after deleting an edge, the states with an in-degree of 0 appear in the same stage. Thus, finding the optimal path on the graph is the solution to the dynamic programming problem.
Scope of Application of Dynamic Programming
Dynamic programming is used to solve multi-stage decision optimization problems, but not all optimization problems can be solved with dynamic programming, right?
Generally, if a problem appears to seek an optimal solution, dynamic programming should be considered, but it must also meet two conditions:
Optimal substructure (principle of optimization)
No aftereffect
The principle of optimization is detailed in the shortest path problem below;
What is no aftereffect?
It means that when solving state i, state j is used, and state j uses state k... state N.
When seeking state N, state i is used, thus forming a cycle in the process of solving states, making it impossible to solve with dynamic programming. This is also the reason for the acyclic nature of the graph understood through graph theory in dynamic programming.
In other words, the current state is a perfect summary of the previous states, and the present is unrelated to the past...
Of course, if you change the way to partition states or stages, it can still satisfy no aftereffect, and such problems can still be solved with dynamic programming.
General Idea for Solving Problems with Dynamic Programming.
After obtaining a multi-stage decision optimization problem, the first step is to determine whether this problem can be solved with dynamic programming. If not, consider search or greedy methods. Once it is determined that the problem can be solved with dynamic programming, the following methods should be used to solve the problem:
(1) Model matching method:
The first consideration is this method. Digging into the essence of the problem, if you find that the problem is a familiar basic model, apply it directly, but be careful with some small changes. Nowadays, exam questions often involve basic model transformations, so be cautious and think twice. These basic models will be introduced one by one in the previous classification.
(2) Three-element method
Carefully analyze the problem and try to determine the three elements of dynamic programming. Different problems have different determination directions:
First determine the stage: number tower problem, and walking problem (see the solution report for details)
First determine the state: most are determined by the state first.
First determine the decision: knapsack problem (see the solution report for details).
Generally, start from the more obvious places. As for how to know which is obvious, that’s an experience issue; doing more problems will help you discover it.
(3) Finding patterns:
This method is very simple. After patiently pushing a few sets of data, look for their patterns and summarize the commonalities between the patterns, which has a bit of a greedy feel to it.
(4) Boundary condition method
Find the boundary conditions of the problem, and then consider the relationship between the boundary conditions and their adjacent states. This method is also very effective.
(5) Relaxing constraints and adding constraints
This idea was seen in Chen Qifeng's paper, specifically adding some conditions or removing some conditions to clarify the problem.
Section 2 Classification Discussion of Dynamic Programming
Here, dynamic programming is classified by state dimensions:
State is one-dimensional
1.1 Decreasing/non-decreasing subsequence problem:
Problem description: {Digging into the essence of the problem, once abstracted into this description, it can be solved with this method}
In an unordered sequence a1, a2, a3, a4...an, find the longest subsequence satisfying: ai<=aj<=ak...<=am, and i<j<k...aj>ak...>am, and i>j>k...>m. (Longest decreasing subsequence).
Problem analysis:
If in the first i-1 numbers ak is used (ak>ai or akai (or aj<=ai), opt[j]+1 is the value of opt[i]; represented by the equation: {I am used to this writing style, but it is not the standard writing style for state transition equations}
opt[i]=max(opt[j])+1 (0<=j<i and aj<=ai) {Longest non-decreasing subsequence}
opt[i]=max(opt[j])+1 (0<=j_ai) {Longest decreasing subsequence}
Implementation of the solving part of the code:
opt[0]:=maxsize; {maxsize is maxlongint or -maxlongint}
for i:=1 to n do
for j:=0 to i-1 do
if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if opt[i]>ans then ans:=opt[i]; {ans is the final solution}
Complexity: From the above implementation, it is not difficult to see that the time complexity is O(N^2), and the space complexity is O(N);_

Example 1 Intercepting Missiles (missile.pas/c/cpp) Source: NOIP1999 (Advanced Group) First Problem
【Problem Description】
A certain country has developed a missile interception system to defend against enemy missile attacks. However, this missile interception system has a flaw: although its first missile can reach any height, each subsequent missile cannot be higher than the previous missile. One day, radar detected an incoming enemy missile. Since the system is still in the trial phase, there is only one set of the system, so it may not be able to intercept all missiles.
Input the heights of the missiles flying in sequence (the height data provided by the radar is a positive integer not exceeding 30000), and calculate the maximum number of missiles that this system can intercept. If all missiles are to be intercepted, how many sets of this missile interception system are needed at a minimum.
【Input File】missile.in
A single line lists the heights of the missiles flying in sequence.
【Output File】missile.out
Two lines, respectively, the maximum number of missiles that can be intercepted, and the minimum number of systems needed to intercept all missiles.
【Input Sample】
389 207 155 300 299 170 158 65
【Output Sample】
6
2
【Problem Analysis】
Experienced competitors can easily see that this is a longest non-increasing subsequence problem, and the standard algorithm is dynamic programming.
Taking the order of the missiles flying in sequence as stages, design the state opt[i] to represent the maximum number of missiles that can be intercepted among the first i missiles.
State transition equation:
opt[i]=max(opt[j])+1 (h[i]>=h[j],0=<j_=a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
anslen:=0;
for i:=1 to n do
if opt[i]>anslen then
anslen:=opt[i];
fillchar(opt,sizeof(opt),0);
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]>a[i]) then
opt[i]:=opt[j]+1;
anstime:=0;
for i:=1 to n do
if opt[i]>anstime then
anstime:=opt[i];
end;
procedure print;
begin
writeln(anslen);
writeln(anstime);
close(input);
close(output);
end;
begin
init;
main;
print;
end._

Example 2 Chorus Formation (chorus.pas/c/cpp) Source: NOIP2004 (Advanced Group) First Problem
N students stand in a row, and the music teacher wants to ask (N-K) students to step out so that the remaining K students can form a chorus formation.
A chorus formation is a formation such that if the K students are numbered from left to right as 1, 2..., K, their heights are T1, T2, ..., TK, then their heights satisfy T1 < ... Ti+1 > ... > TK (1 <= i <= K).
Your task is to calculate the minimum number of students that need to step out so that the remaining students can form a chorus formation, given the heights of all N students.
【Input File】
The first line of the input file is an integer N (2 <= N <= 100), indicating the total number of students. The first line contains N integers separated by spaces, where the i-th integer Ti (130 <= Ti <= 230) is the height of the i-th student (in centimeters).
【Output File】
The output file chorus.out contains a single line with a single integer, which is the minimum number of students that need to step out.
【Sample Input】
8
186 186 150 200 160 130 197 220
【Sample Output】
4
【Data Scale】
For 50% of the data, it is guaranteed that n <= 20;
For all data, it is guaranteed that n <= 100.
【Problem Analysis】
The minimum number of students stepping out means that the remaining students are maximized, which means the longest sequence.
This analysis is a typical longest decreasing subsequence problem. Just enumerate the optimal solution that can be obtained when each person stands in the middle.
Clearly, it is equal to finding the longest increasing subsequence to the left and the longest decreasing subsequence to the right, including him.
Let’s look at the complexity:
The complexity of calculating the longest decreasing subsequence is O(N^2), and since we need to find N times, the total complexity is O(N^3). This complexity is acceptable for the data range of this problem. But is there a better method?
In fact, the longest subsequence can be found in one go. Because the longest decreasing (increasing) subsequence is not affected by the middle person.
Just use OPT1 to find the longest increasing subsequence once, and OPT2 to find the longest decreasing subsequence once. Thus the answer is N - max(opt1[i] + opt2[i] - 1).
The complexity is reduced from O(N^3) to O(N^2).

【Source Code】
program chorus;
const
fin='chorus.in';
fout='chorus.out';
maxn=200;
var
opt1,opt2,a[0..maxn] of longint;
n,ans;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j;
begin
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt1[i]) then
opt1[i]:=opt1[j]+1;
a[n+1]:=-maxlongint;
for i:=n downto 1 do
for j:=i+1 to n+1 do
if (a[j]opt2[i]) then
opt2[i]:=opt2[j]+1;
ans:=0;
for i:=1 to n do
if opt1[i]+opt2[i]>ans then
ans:=opt1[i]+opt2[i];
end;
procedure print;
begin
writeln(n-ans+1);
close(input);
close(output);
end;
begin
init;
main;
print;
end.

Example 3 Buy Low Buy Lower (buylow.pas/c/cpp) Source: USACO 4-3-1
【Problem Description】
"Buy low" is a successful secret in stock trading. If you want to become a successful investor, you must follow this secret:
"Buy low, buy lower"
This means that every time you buy stocks, the price must be lower than the last time you bought. The more times you buy stocks according to this rule, the better. See how many times you can buy stocks at most according to this rule.
Given the stock prices for N consecutive days, you can buy stocks on any day, but the price at the time of purchase must be lower than the last purchase price. Write a program to find out how many times you can buy stocks at most.
For example, the stock prices for several days are:
Days 1 2 3 4 5 6 7 8 9 10 11 12
Prices 68 69 54 64 68 64 70 67 78 62 98 87
In this example, a smart investor (according to the above definition) can buy stocks at most 4 times if the price at each purchase is lower than the last purchase price. One way to buy is as follows (there may be other ways):
Days 2 5 6 10
Prices 69 68 64 62
【Input File】buylow.in
The first line: N (1 <= N =a[j],0=<j<i) {a[i] stores the stock price on the i-th day}
The maximum opt[i] is the final solution.
The second question is a bit more troublesome.
Considering the boundary of the problem, when the first question obtains an optimal solution opt[i]=X,
If there is another opt[j]=x in 1 to N, then selecting this scheme of J must be valid.
Is it true that counting all opt[j]=x is the solution?
It is obviously not that simple, because selecting the stock on day J does not necessarily equal 1, as shown in the following example:
5 6 4 3 1 2
Scheme one: 5431
Scheme two: 5432
Scheme three: 6431
Scheme four: 6432
x=4
This means that although opt[5]=X and opt[6]=X, the count is only two, while there should actually be four schemes. However, upon careful observation, it is found that in the scheme that forms opt[5]=x, the number of schemes for opt[j]=x-1 is two, for opt[j]=x-2 is one, for opt[j]=x-3 is one...
Clearly, this satisfies the low definition of design function F(i) to represent the number of schemes using the i-th stock in the first I stocks.
Recursion:
1 (i=0)
F(i)=
Sum(F(j)) (0<=ja[i],opt[j]=opt[i]-1) {sum represents summation}
The answer=sum(F(j)) {0<ja[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
for i:=1 to n do
begin
j:=i-1;
while (j>0) and ((opt[i]opt[j]) or (a[i]a[j])) do
dec(j);
next[i]:=j;
end;
F[0,1]:=1;
for i:=1 to n+1 do
for j:=i-1 downto next[i] do
if (opt[j]=opt[i]-1) and (a[j]>a[i]) then
Hinc(F[i],F[j]);
end;
procedure print;
var
i,top,m;
begin
write(opt[n+1]-1,' ');
top:=maxsize;
while (top>1) and (F[n+1][top]=0) do
dec(top);
write(F[n+1,top]);
for i:=top-1 downto 1 do
begin
m:=F[n+1,i];
while m<maxsize div 10 do
begin
write('0');
m:=m*10;
end;
write(F[n+1,i]);
end;
writeln;
close(input);
close(output);
end;
begin
init;
main;
print;
end.

Example 4 Ships (ships.pas/c/cpp) Source: "Classic of Aose" (Advanced Edition)
【Problem Description】
The country of PALMIA is divided into two banks by a river, with N villages on each bank. Each village on the north bank has a unique friend on the south bank, and their friend villages are different from each other.
Each pair of friend villages wants a boat to connect them, and they apply to the government for approval. Due to frequent fog on the river, the government decides to prohibit intersecting boat routes (if they intersect, it is likely to cause collisions).
Your task is to write a program to help government officials decide which boat routes to approve so that the number of non-intersecting routes is maximized.
【Input File】ships.in
The input file consists of several sets of data. The first line of each data set contains two integers X and Y, separated by a space, where X represents the length of the PALMIA river (10 <= X <= 6000) and Y represents the width of the river (10 <= Y <= 100). The second line contains an integer N, indicating the number of villages on both banks. In the next N lines, each line contains two non-negative integers C and D, separated by a space, representing the distance of this pair of friend villages from the westernmost boundary of the PALMIA river (C represents the village on the north bank, D represents the village on the south bank). There are no villages on the same bank at the same position. The last set of data is indicated by a line containing two zeros, separated by a space.
【Output File】ships.out
For each set of data in the input file, the output file should indicate the maximum number of boat routes that can be approved under the above conditions on consecutive lines.
【Sample Input】
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
【Sample Output】
4
【Problem Analysis】
This problem is relatively difficult to think about, and it is not immediately clear what the essence of the problem is. Here I recommend two methods for thinking about such problems.
Method 1: Finding Patterns (the third method I summarized earlier)
To find patterns, you naturally need to push a few sets of data, and of course, start with the sample;

Carefully observe the above figure: the red routes are legal, so what rules do they satisfy?
C1 C2 C3 C4
The endpoints of the red lines on the north bank: 4 9 15 17
The endpoints of the red lines on the south bank: 2 8 12 17
D1 D2 D3 D4
It is not difficult to see that regardless of the slope of the line, there is such a rule:
C1<C2<C3<C4 and D1<D2<D3<D4
If we sort the input data in ascending order, the problem becomes abstract:
Find the longest subsequence in a sequence (D) that satisfies DI<DJ<Dk... and i<j<k
In this case, it is a typical longest non-decreasing subsequence problem...
Method 2: Boundary Condition Method (the fourth method I summarized earlier)
The boundary method is actually about shrinking the data down. Clearly, when N=1, the answer is 1. What about N=2?
Consider such a set of data:
N=2
C1 D1
C2 D2
When C1D2, they will definitely intersect; conversely, they will not intersect.
When C1 >C2, if D1<D2, they will definitely intersect; otherwise, they will not intersect.
N=3
C1 D1
C2 D2
C3 D3
...
Actually, there is no need to derive N=3; if you are interested, you can derive it. Just looking at N=2 can lead to the conclusion:
For any two routes, if they satisfy Ci<Cj and Di<Dj, then the two routes do not intersect. Thus, to ensure that all routes do not intersect in a sequence, it is necessary to satisfy C1<C2<C3...Cans and D1<D2<D3...<Dans, which means sorting C and finding the length of the longest sequence that satisfies this condition is the solution.
After this analysis, it is clear that this is a longest non-decreasing subsequence problem.
Complexity: Sorting can be done with O(nlogn) algorithms, and the time complexity for finding the longest non-decreasing subsequence is O(n^2).
The total complexity is O(n^2).

【Source Code】
program ships;
const
fin='ships.in';
fout='ships.out';
maxn=5010;
type
retype=record
C,D;
end;
var
x,y,n,ans;
a[0..maxn] of retype;
opt[0..maxn] of longint;
procedure init;
var
i;
begin
readln(n);
for i:=1 to n do
read(a[i].c,a[i].d);
end;
procedure quick(L,r);
var
i,j,x;
y;
begin
i:=L;
j:=r;
x:=a[(i+j) div 2].c;
repeat
while a[i].cx do
dec(j);
if ij;
if j>L then quick(L,j);
if i<r then quick(i,r);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
quick(1,n);
for i:=1 to n do
for j:=0 to i-1 do
if (a[j].dopt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if ans<opt[i] then
ans:=opt[i];
writeln(ans);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(x,y);
while (x+y0) do
begin
init;
main;
read(x,y);
end;
close(input);
close(output);
end.

1.2 Knapsack Problem
First, let's talk about the basic model of the knapsack problem:
There are N items, each with a value of V and a weight of W. The goal is to pack these items into a knapsack with a capacity of S, maximizing the total value of the items packed.
The knapsack problem can be solved using greedy and search methods, but the results are not satisfactory. However, I will discuss this in my summary of greedy and search methods. The standard solution is dynamic programming, and I am accustomed to designing a one-dimensional state for this problem, although a two-dimensional state can also be designed, which will be discussed below. For now, let's discuss solving the knapsack problem using a one-dimensional state.
Classification of the knapsack problem:
(1) Fractional knapsack: The weight of the items is real numbers, such as oil, water, etc., which can be taken in fractions like 1.67 liters...
(2) Integer knapsack: 0/1 knapsack: Each item can only be selected once or not at all. You cannot select only a part of it.
Partial knapsack: The selected items can be a part of the total.
(3) Multiple knapsack: There is more than one knapsack.
Fractional knapsack: This will be discussed in detail in the greedy summary.
Integer knapsack:
Partial knapsack: Same as fractional knapsack.
0/1 knapsack: This problem is the most frequently encountered problem and should be mastered.
Let's first look at a simplified version of the 0/1 knapsack problem:
There are N items, each with a weight of W. Can these items exactly fill a knapsack with a capacity of S (i.e., the total weight equals S)? If not, what is the maximum weight that can be achieved?
For this problem, we can divide the items by their count and design a state opt[i] to indicate whether the knapsack with a weight of i can be filled. Clearly, the base type of opt[i] is boolean.
What is the decision?
When packing the i-th item, if the previous i-1 items can fill a knapsack with weight k, then the knapsack with weight k+w[i] can also be filled. Thus, for an opt[j], as long as opt[j-w[i]] is true (indicating it can be filled), then opt[j] can also be filled, but note that when enumerating the knapsack's weight for each item, if this forward deduction is done, the same item may be used multiple times, because if k+w[i] can be filled, then k+w[i]+w[i] can also be filled, but in reality, it cannot be filled because there is only one item. This issue can be easily resolved by simply deducing in reverse.
Thus, dividing stages and designing states satisfies the no aftereffect condition.
Clearly, for each stage, they are independent, and the order of items does not affect the solution since the order of packing items is not limited. For opt[j], only opt[j-w[i]] is considered without considering the subsequent items, so it satisfies the no aftereffect condition.
With the above analysis, it is not difficult to write the state transition equation:
opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
Time complexity:
Number of stages O(S) * Number of states (O(N)) * Transition cost (O(1)) = O(SN)
Now let's look at a few example problems:

Example 5 Packing Problem (pack.pas/c/cpp) Source: NOIP2001 (Popular Group) Fourth Problem
【Problem Description】
There is a box with a capacity of V (positive integer, 0 <= V <= 20000), and there are n items (0 < n <= 30), each with a volume (positive integer).
The task is to pack any number of items from these n items into the box, minimizing the remaining space in the box.
【Input File】
The first line contains a positive integer V indicating the box's capacity, the second line contains a positive integer N indicating the number of items, followed by N lines listing the volumes of these N items.
【Output File】
A single line indicating the minimum remaining space in the box.
【Input Sample】
24
6
8
3
12
7
9
7
【Output Sample】
0
【Problem Analysis】
This problem is a classic 0/1 knapsack problem and is a simplified version of the 0/1 knapsack. Treat the box as the knapsack, the capacity as the load, and the volume as the weight. The minimum remaining space means to fill the knapsack as much as possible. Thus, this problem becomes:
Given a knapsack with a load of V, and N items, pack as many items as possible to maximize the weight of the knapsack.
Design a state opt[i] to indicate whether weight i can be formed.
State transition equation: opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
The final solution is v-x (x <= n and opt[x]=true and opt[x+1..n]=false).

【Source Code 1】
program pack;
const
fin='pack.in';
fout='pack.out';
maxv=20010;
maxn=100;
var
opt[0..maxv] of boolean;
w[0..maxn] of longint;
v,n,x;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(v);
read(n);
for i:=1 to n do
read(w[i]);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to n do
for j:=v downto w[i] do
if opt[j-w[i]] then opt[j]:=true;
x:=v;
while not opt[x] do dec(x);
end;
procedure print;
begin
writeln(v-x);
close(input);
close(output);
end;
begin
init;
main;
print;
end.

Example 6 Weighing with Weights Source: NOIP1996 (Advanced Group) Fourth Problem
【Problem Description】
There are weights of 1g, 2g, 3g, 5g, 10g, and 20g, each with several pieces (total weight <= 1000), and the task is to find out how many different weights can be weighed using these weights.
【Input File】
a1 a2 a3 a4 a5 a6
(Indicating that there are a1 pieces of 1g weights, a2 pieces of 2g weights, ..., a6 pieces of 20g weights, separated by spaces).
【Output File】
Total=N
(N represents the number of different weights that can be weighed using these weights, but does not include the case of using no weights).
【Input Sample】
1 1 0 0 0 0
【Output Sample】
TOTAL=3
【Problem Analysis】
This problem is a slight modification of the previous problem, where the weights of a1+a2+a3+a4+a5+a6 are w[i], w[i] ∈ {1,2,3,5,10,20}. The weights can be equal, and the task is to find out the number of different weights that can be weighed using these weights.
This modification makes it a simplified version of the classic 0/1 knapsack problem, and the solving method is completely the same as mentioned above. However, it should be noted that this problem is not about finding the maximum load but counting all the weights that can be weighed.

【Source Code 1】
program P4;
const
maxn=1010;
w[1..6] of longint=(1,2,3,5,10,20);
var
opt[0..maxn] of boolean;
a[1..6] of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.

Example 7 Building a Castle Source: vijos P1059
【Problem Description】
Little XC, the son of XC, loves to play with building blocks to build beautiful castles. The castle is made up of some cubic blocks, and each layer of the castle is a block. Little XC is smarter than his father XC, and he discovered that when building the castle, if the block below is larger than the block above, the castle is less likely to fall. So he always follows this rule when building the castle.
Little XC wants to give the castle he built to the pretty girls in kindergarten, which will increase his favorability. To be fair, he decides to give each girl a castle of the same height to avoid disputes among the girls over who gets the prettier castle. However, he finds that he did not consider this in advance while building the castle. So now he wants to modify the castle. Since he has no extra blocks, he comes up with a clever modification plan. He decides to remove some blocks from each castle so that in the end, each castle is of the same height. To make his castle more magnificent, he thinks the final castles should be as tall as possible.
Task:
Please help Little XC write a program to determine which blocks should be removed based on the information of all the castles he built to achieve the best effect.
【Input File】
The first line is an integer N (N0 do
begin
inc(top);
a[top]:=m;
inc(tothig,m);
read(m);
end;
for i:=1 to top do
for j:=tothig downto 1 do
if (j-a[i]>=0) and (opt[ii,j-a[i]]) then
opt[ii,j]:=true;
end;
ans:=maxhig;
while not opt[1,ans] do
dec(ans);
while not can(ans) do
dec(ans);
writeln(ans);
end;
begin
init;
main;
end.

Reviewing the above content fully illustrates that the essence of dynamic programming is recursion. In fact, according to my understanding (dynamic programming involves optimal decisions, recursion is purely summarizing), the simplified version of the knapsack problem is more accurately considered recursion rather than dynamic programming. As for the boundary between dynamic programming and recursion, it is inherently vague (at least I think so), and it can be viewed as anything without the need to nitpick.
Returning to the original problem of the 0/1 knapsack (if you forgot, refer to the above).
If we do not know this model, how do we approach this problem?
This requires using the second method mentioned in the first section: the three-element method.
The problem clearly states that for an item, you either take it or leave it, which means the decision is to not take it (represented by 0) or take it (represented by 1). Thus, it is clear what the decision is, which is also the breakthrough for this problem. Knowing the decision, writing a search program should be quite easy.
So what is the stage?
Clearly, given a bunch of items to pack into the bag, you are taking them one by one. Thus, the stage is evidently the number of items.
What about the state?
Some people have a habit (like me) of classifying items first and then packing similar items into small bundles before putting the small bundles into the bag. We can think of this idea as preparing many small bundles in increasing order of weight, such as preparing small bundles with weights of 1, 2, 3, 4, and 5 for a bag with a weight of 6. Thus, the state can be thought of as:
Design a state opt[i,j] to represent the maximum value that can be obtained when packing the i-th item into a bag with a weight of j.
opt[i-1,j] (j-w[i]0)
State transition equation: opt[i,j]=
max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]} (j-w[i]>=0,i>0)
(w[i]: weight of the i-th item, v[i]: value of the i-th item)
Explanation: To fill a bag with a weight of j, you need to leave space for w[i] (j-w[i]) and put the i-th item in, which is greater than the value obtained by not putting it in.
Boundary condition: opt[0,i]=0; (i∈{1..S})
Note:
This two-dimensional state representation will be discussed in the next section, but for the sake of understanding, I will mention it here.
The above method clearly shows the three elements of dynamic programming, and the implementation is quite simple. However, when I first learned about the knapsack problem, I used another one-dimensional state representation method.
Using the fifth method mentioned in the first section (relaxing constraints and adding constraints) to rethink this problem:
How to relax the constraints?
Remove the value from the problem, and not considering the value makes the optimal problem a simplified version of the knapsack problem. What insights does this simplified version provide us?
Once again, adding constraints: the knapsack must be filled.
Clearly, among the plans to fill the knapsack, finding one with the maximum value is the solution to the problem. What about not filling the knapsack? In fact, filling the knapsack must reach a certain weight (X). We can treat this situation as filling a small bag with a weight of X.
To summarize the above thought process:
Relaxing constraints allows us to find the breakthrough of the problem—similar to the simplified version of the knapsack problem, we can determine whether a knapsack with a load of S can be filled.
Adding constraints allows us to find the solution method—selecting the optimal plan among the filled knapsack plans.
Thus, the problem is solved.
Design a state opt[j] to represent the maximum value that can be obtained when filling a bag with a weight of j. For the i-th item, as long as opt[j-w[i]] can be filled and opt[j-w[i]]+v[i] is greater than opt[j], then put this item in (update opt[j]).
How to make opt[j] have both the concept of whether it can be formed and the optimal concept?
opt[j] only represents the optimal, just make the initial condition +1, checking whether opt[j] is 0. If opt[j]=0, it indicates that j cannot be filled.
Boundary condition: opt[0]=1;
State transition equation: opt[j]=max{opt[j-w[i]]} (0<i<n,w[i]<=j<=S)
Problem solution: ans=max{opt[i]}-1 (0<i<=s)
Time complexity: Number of stages O(S) * Number of states (O(N)) * Transition cost (O(1)) = O(SN)
Now let's look at a few example problems:

Example 8 Medicinal Herbs (medic.pas/c/cpp) Source: NOIP2005 (Popular Group) Third Problem
【Problem Description】
Chen Chen is a gifted child, and his dream is to become the greatest doctor in the world. To achieve this, he wants to apprentice with the most prestigious doctor nearby. The doctor, to assess his qualifications, presents him with a challenge. The doctor takes him to a cave filled with herbs and says, "Child, there are various herbs in this cave, and picking each one requires some time, and each herb has its own value. I will give you a period of time during which you can pick some herbs. If you are a smart child, you should be able to maximize the total value of the herbs you pick."
If you were Chen Chen, could you complete this task?
【Input File】
The first line of the input file contains two integers T (1 <= T <= 1000) and M (1 <= M <= 100), separated by a space, where T represents the total time available for picking herbs, and M represents the number of herbs in the cave. The next M lines each include two integers between 1 and 100 (inclusive), representing the time required to pick a certain herb and the value of that herb.
【Output File】
The output file medic.out contains a single line with a single integer, indicating the maximum total value of the herbs that can be picked within the specified time.
【Input Sample】
70 3
71 100
69 1
1 2
【Output Sample】
3
【Data Scale】
For 30% of the data, M <= 10;
For all data, M <= 100.
【Problem Analysis】
The first step is to analyze the problem and determine whether it can be solved with dynamic programming. If it can, we can use the state transition method to solve it.
The state transition equation can be represented as:
opt[j]=max(opt[j-w[i]]+v[i]) (0<=j-w[i])
The time complexity is O(N*T), where N is the number of herbs and T is the total time available.
The space complexity is O(T).
Now let's look at the source code for this problem:

【Source Code】
program medic;
const
maxn=1010;
var
opt[0..maxn] of longint;
w[0..maxn] of longint;
v,n,t;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(t,n);
for i:=1 to n do
read(w[i],v[i]);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=t downto w[i] do
if opt[j-w[i]]+v[i]>opt[j] then
opt[j]:=opt[j-w[i]]+v[i];
end;
procedure print;
var
ans;
begin
ans:=0;
for i:=1 to t do
if opt[i]>ans then
ans:=opt[i];
writeln(ans);
end;
begin
init;
main;
print;
end.

Example 9 Happy Jinming Source: NOIP2006 (Popular Group) Second Problem
【Problem Description】
Jinming is very happy today because he is about to get the keys to his new house, which has a spacious room just for him. What makes him even happier is that his mother told him yesterday, "You can decide what items to buy for your room and how to arrange them, as long as it does not exceed N yuan." Early this morning, Jinming started budgeting, but he wants to buy too many things, which will definitely exceed his mother's limit of N yuan. Therefore, he assigns an importance level to each item, dividing them into 5 levels: using integers 1 to 5, with level 5 being the most important. He also found out the prices of each item on the internet (all are integers). He hopes to maximize the total sum of the prices multiplied by their importance while ensuring that the total cost does not exceed N yuan (it can equal N yuan).
Let the price of the j-th item be v[j] and its importance be w[j]. If k items are selected, numbered j1...jk, the total sum is:
v[j1]*w[j1]+...+v[jk]*w[jk]. Please help Jinming design a shopping list that meets the requirements.
【Input File】
The first line contains two positive integers, N and m (where N (<30000) represents the total amount of money, and m (<25) is the number of items he wants to buy).
From the second line to the m+1 line, each line gives two non-negative integers v p (where v represents the price of the item (v ≤ 10000), and p represents the importance of the item (1~5)).
【Output File】
The output contains only one positive integer, which is the maximum value of the total price multiplied by importance of the items that can be bought without exceeding the total amount of money.
【Sample Input】
5 4
1 2
2 1
2 2
2 2
【Sample Output】
13
【Problem Analysis】
The problem description is quite clear, and it is about maximizing the total value while adhering to the constraints. The dynamic programming approach is appropriate here.
The state transition equation can be represented as:
opt[j,k]=max{opt[j-v[i],k-rp[i]]+1}
(rmb[i]<=j<=m,rp[i]<=k<=r,0<i0)
ct[j,k]:=min{ct[j-rmb[i],k-rp[i]]}+time[i] (opt[j,k]=opt[j-rmb[i],k-rp[i]]+1)
Time complexity: Number of stages O(N) * Number of states O(MR) * Transition cost O(1) = O(NMR)
Note: The data is quite small.
The problem extension:
If other conditions are added, such as requiring a certain SP to buy items, then the state will need to add another dimension, and each additional condition will add another dimension.

【Source Code】
program gf;
const
fin='gf.in';
fout='gf.out';
maxn=110;
var
rmb,rp,time[0..maxn] of longint;
opt,ct[0..maxn,0..maxn] of longint;
n,m,r,ans,max;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n);
for i:=1 to n do
read(rmb[i],rp[i],time[i]);
read(m,r);
close(input);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),0);
fillchar(ct,sizeof(ct),0);
opt[0,0]:=1;
for i:=1 to n do
for j:=m downto rmb[i] do
for k:=r downto rp[i] do
if opt[j-rmb[i],k-rp[i]]>0 then
begin
if opt[j-rmb[i],k-rp[i]]+1>opt[j,k] then
begin
opt[j,k]:=opt[j-rmb[i],k-rp[i]]+1;
ct[j,k]:=ct[j-rmb[i],k-rp[i]]+time[i];
end
else if (opt [j,k]=max) and (ct [j,k] 0），打分越高的碟說明多多越愛看。每張碟有播放的時間 Ti。多多想在今晚爺爺規定的時間裡看的碟總分最高。（必須把要看的碟看完，也就是說一張碟不能只看一半）。顯然叔叔在買碟是沒必要把 N 張全買了，只要買要看的就 OK 了，這樣節省資金啊。而且多多讓叔叔慣的特別任性只要他看到有幾張就一定會看完。
可是出現了一個奇怪的問題，買碟的地方只買給顧客 M（M<N）張碟，不會多也不會少。這可讓多多叔叔為難了。怎麼可以在 N 張碟中只買 M 張而且在規定時間看完，而且使總價值最高呢？
聰明的你幫幫多多的叔叔吧。
【輸入說明】(watchdvd.in)
輸入文件有三行
第一行：兩個數空格隔開的正整數，N，M，L（分別表示叔叔給多多買的碟的數量，商店要買給叔叔的碟的數量，爺爺規定的看碟的時間段）。
第二行到第 N 行，每行兩個數：T，M，給出多多列表中 DVD 碟的信息。
【輸出說明】(watchdvd.out)
單獨輸出一行
表示多多今晚看的碟的總分。
如果商店賣給叔叔的 M 張碟無法在爺爺規定的時間看完輸出 0；
【輸入樣例】
3 4
1 2
2 1
2 2
2 2
【輸出樣例】
13
【數據範圍】
20% 的數據 N <=20; L<=2000;
100% 的數據 N <=100 L <=2000; M y then max:=x;
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=m downto 1 do
if j0) or ((j=1) and (k=w[i])) then
opt[j,k]:=max(opt[j-1,k-w[i]]+val[i],opt[j,k]);
ans:=-maxlongint;
for i:=0 to v do
if opt[m,i]>ans then ans:=opt[m,i];
end;
procedure print;
begin
write(ans);
close(output);
end;
begin
init;
main;
print;
end.

3. 多維狀態和動態規劃的優化
一般多維動態規劃的時，空間複雜度較高，所以我們要想辦法將其優化，我就把多維動態規劃和動態規劃的優化放到一起了……
多維動態規劃以三，四維最為常見，在多的也沒有太大的研究價值，其實多維動態規劃大多也就是上面的一維，和二維的加一些條件，或是在多進程動態規劃中要用到。當然除了這些特點外，狀態的表示也有一些共性。
三維：狀態 opt [i,j,k] 一般可表示下面的含義：
（1）二維狀態的基礎上加了某個條件，或其中一維變成兩個。
比如 opt [L,i] 表示起點為 I，長度為 L 的序列的最優值。opt [L,i,j] 就可表示起點是 i 和起點是 j，長度是 L 的兩個序列的最優值。
（2）I，J，K 組合表示一個正方形（（i,j）點為一角，邊長為 K）。
（3）I，J，K 組合表示一個等邊三角形（（i,j）點為一角，邊長為 K）。
（4）四維：除了二維和三維加條件外，還可以用 i,j,k,t 組合來描述一個矩形，
（i,j）點和（k,t）點是兩個對頂點。
（5）四維以上的一般都是前幾維加了條件了，這裡就不多說了。
動態規劃的優化：
動態規劃的優化往往需要較強的數學功底。
常見空間優化：
滾動數組，滾動數組在前面也提到過，其實很簡單，如果一個狀態的決策的步長為 N 就只保留以求出的最後 N（一般 N=1）個階段的狀態，因為當前狀態只和後 N 個階段中的狀態有關，再以前的已經利用過了，沒用了就可以替換掉了。具體實現是最好只讓下標滾動（這樣更省時間）。
X：=K1，K1：=K2，K2；=K3，K3：=X 這樣就實現了一個 N=3 的下標的滾動，在滾動完如果狀態是涉及累加，累乘類的操作要注意將當前要求的狀態初始化。
常見時間優化：利用一些數據結構（堆，並查集，HASH）降低查找複雜度。
時間空間雙重優化：改變狀態的表示法，降低狀態維數。
具體的多維動態規劃和動態規劃的優化，我們從題目裡體會吧！
3.1 矩陣問題
先看一道題
例題 27 蓋房子來源：VIJOS P1057
【問題描述】
永恆の靈魂最近得到了面積為 n*m 的一大塊土地（高興 ING^_^），他想在這塊土地上建造一所房子，這個房子必須是正方形的。
但是，這塊土地並非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。這些瑕疵十分噁心，以至於根本不能在上面蓋一磚一瓦。
他希望找到一塊最大的正方形無瑕疵土地來蓋房子。
不過，這並不是什麼難題，永恆の靈魂在 10 分鐘內就輕鬆解決了這個問題。現在，您也來試試吧。
【輸入文件】
輸入文件第一行為兩個整數 n,m（1<=n,m<=1000），接下來的每行 m 個數字，用空格隔開。0 表示該塊土地有瑕疵，1 表示該塊土地完好。
【輸出文件】
一個整數，最大正方形的邊長。
【輸入樣例】
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
【OUTPUT SAMPLE】
2
【問題分析】
題目中說要求一個最大的符合條件的正方形，所以就想到判斷所有的正方形是否合法。
這個題目直觀的狀態表示法是 opt [i,j,k] 基類型是 boolean，判斷以（i,j）點為左上角（其實任意一個角都可以，依據個人習慣）, 長度為 K 的正方形是否合理，再找到一個 K 值最大的合法狀態就可以了（用 true 表示合理，false 表示不合理）。其實這就是遞推，（決策唯一）。
遞推式：
opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1)
時間複雜度：
狀態數 O（N3）* 轉移代價 O（1）= 總複雜度 O（N3）
空間複雜度：
O（N3）
由於空間複雜度和時間複雜度都太高，不能 AC，我們就的再想想怎麼優化？
顯然何以用滾動數組優化空間，但是時間複雜度仍然是 O（N3）。這就需要我們找另外一種簡單的狀態表示法來解了。
仔細分析這個題目，其實我們沒必要知道正方形的所有長度，只要知道以一個點為左上角的正方形的最大合理長度就可以了。
如果這個左上角是 0 那麼它的最大合理長度自然就是 0（不可能合理）。
如果這個左上角是 1 呢？
回顧上面的遞推式，我們考慮的是以它的右面，下面，右下這個三個方向的正方形是否合理，所以我們還是要考慮這三個方向。具體怎麼考慮呢？
如果這三個方向合理的最大邊長中一個最小的是 X，那麼它的最大合理邊長就是 X+1。為什麼呢？
看個例子：
0 1 1 1 1 1
1 1 1 1 1 1
0 1 0 1 1 0
1 1 0 1 1 1
上例中紅色的正方形，以（1,3）點為左上角，以（1，4），（2，3），（2，4）這三個點的最大合理邊長分別是 2，1，2。其中最小的是以（2，3）為左上角的正方形，最大合理邊長是 1。因為三個方向的最大合理邊長大於等於 1，所以三個方向上邊長為 1 的正方形是合理的，即上面低推式中:
opt [1,3,2]=opt [1,4,1] and opt [2,3,1] and opt [2,4,1] and (a [1,3]=1) = true 成立
這樣就把一個低推判定性問題轉化成最優化問題從而節省空間和時間。
具體實現：
設計一個狀態 opt [i,j] 表示以（i,j）為左上角的正方形的最大合理邊長。
狀態轉移方程：
min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1 (a[i,j]=1)
opt[i,j]=0 (a[i,j]=0)
時間複雜度：狀態數 O（N2）* 轉移代價 O（1）= 總代價 O（N2）
空間複雜度：O（N2）

【源代碼】
program P1057;
const
maxn=1010;
var
opt,a[0..maxn,0..maxn] of longint;
n,m,ans;
procedure init;
var
i,j;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
for i:=n downto 1 do
for j:=m downto 1 do
if a[i,j]0 then
begin
opt[i,j]:=opt[i+1,j];
if opt[i,j+1]<opt[i,j] then
opt[i,j]:=opt[i,j+1];
if opt[i+1,j+1]ans then ans:=opt[i,j];
writeln(ans);
end;
begin
init;
main;
end.

3.2 Multi-process Dynamic Programming
From the literal meaning, multi-process refers to the requirement of maximizing the total sum of a problem that needs to be repeated multiple times based on the original problem.
Let’s look at an example:
Example 28 Grid Number Picking (fgqs.pas/c/cpp) Source: NOIP2000 (Advanced Group)
【Problem Description】
There is an NN grid (N<=10), and some cells in this grid are filled with positive integers, while others contain the number 0.
A person starts from point A at the top left of the grid and can move down or to the right until reaching point B at the bottom right. Along the way, he can collect the numbers in the cells (the cells become 0 after being collected).
This person must find two paths from point A to point B such that the sum of the numbers collected is maximized.
【Input File】
The first line contains an integer N (indicating the NN grid), followed by N lines, each containing N integers separated by spaces. 0 indicates that the cell has a flaw, while 1 indicates that the cell is intact.
【Output File】
An integer representing the maximum length of the largest square.
【Input Sample】
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
【Output Sample】
2
【Problem Analysis】
The problem states that we need to find the largest valid square, so we think about whether all squares are valid.
This problem's intuitive state representation is opt[i,j,k] with a base type of boolean, determining whether a square with (i,j) as the top left corner (actually any corner can be used, depending on personal preference) and length K is valid, and then finding the maximum K value that is valid (using true to indicate valid, false to indicate invalid). This is actually recursion (with a unique decision).
Recursion formula:
opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1)
Time complexity:
Number of states O(N^3) * Transition cost O(1) = Total complexity O(N^3)
Space complexity:
O(N^3)
Since both space and time complexity are too high, it cannot be AC, so we need to think about how to optimize it.
Clearly, we can use rolling arrays to optimize space, but the time complexity remains O(N^3). We need to find another simple state representation to solve it.
Upon careful analysis, we realize that we do not need to know all lengths of squares; we only need to know the maximum valid length of the square with a point as the top left corner.
If this top left corner is 0, then its maximum valid length is naturally 0 (impossible to be valid).
If this top left corner is 1?
Recalling the above recursion, we consider whether the squares in the three directions (right, down, and right down) are valid, so we still need to consider these three directions. How do we consider this specifically?
If the maximum valid length in these three directions is X, then its maximum valid length is X+1. Why?
Let’s look at an example:
0 1 1 1 1 1
1 1 1 1 1 1
0 1 0 1 1 0
1 1 0 1 1 1
In the above example, the red square with (1,3) as the top left corner has maximum valid lengths of 2, 1, and 2 for the points (1,4), (2,3), and (2,4) respectively. The minimum is for the square with (2,3) as the top left corner, with a maximum valid length of 1. Since the maximum valid lengths in the three directions are greater than or equal to 1, the square with a length of 1 in the three directions is valid, i.e., the recursion formula above holds:
opt[1,3,2]=opt[1,4,1] and opt[2,3,1] and opt[2,4,1] and (a[1,3]=1) = true
Thus, we transform a decision problem into an optimization problem, saving space and time.
Specific implementation:
Design a state opt[i,j] to represent the maximum valid length of the square with (i,j) as the top left corner.
State transition equation:
min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1 (a[i,j]=1)
opt[i,j]=0 (a[i,j]=0)
Time complexity: Number of states O(N^2) * Transition cost O(1) = Total cost O(N^2)
Space complexity: O(N^2)

【Source Code】
program P1057;
const
maxn=1010;
var
opt,a[0..maxn,0..maxn] of longint;
n,m,ans;
procedure init;
var
i,j;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
for i:=n downto 1 do
for j:=m downto 1 do
if a[i,j]0 then
begin
opt[i,j]:=opt[i+1,j];
if opt[i,j+1]<opt[i,j] then
opt[i,j]:=opt[i,j+1];
if opt[i+1,j+1]ans then ans:=opt[i,j];
writeln(ans);
end;
begin
init;
main;
end.

【Source Code】
program P1057;
const
maxn