Algorithm design of dynamic programming

1: Find out the properties of the optimal solution and describe its structural characteristics

2: Define the optimal value recursively

3: Calculate the optimal value in a bottom-up manner

4: The optimal solution is constructed according to the information obtained when calculating the optimal value

The problem that can be solved by dynamic programming generally has three properties

(1) Optimization principle: if the solution of the subproblem contained in the optimal solution of the problem is also optimal, it is said that the problem has an optimal substructure, that is, it satisfies the optimization principle.

(2) No aftereffect: once the state of a certain stage is determined, it will not be affected by the subsequent decisions of this state. In other words, the process after a certain state will not affect the previous state, but only related to the current state.

(3) Overlapping subproblems: that is, subproblems are not independent, and a subproblem may be used many times in the next stage of decision-making. (this property is not a necessary condition for the application of dynamic programming, but without this property, the dynamic programming algorithm has no advantages over other algorithms.) dynamic programming improves the original search algorithm with exponential time complexity into an algorithm with polynomial time complexity. The key is to solve redundancy, which is the fundamental purpose of dynamic programming algorithm. Dynamic programming is essentially a space for time technology. In the process of implementation, it has to store various states in the generation process, so its spatial complexity is greater than other algorithms.

Using dynamic programming to solve problems, the most important thing is to determine the three elements of dynamic programming

(1) Phase of the problem

(2) Status of each stage

(3) The recursive relationship between the previous stage and the later stage.

Specific steps of dynamic planning:

(1) Stage division: divide the problem into several stages according to the time or space characteristics of the problem. When dividing the stages, pay attention that the divided stages must be orderly or sortable, otherwise the problem cannot be solved.

(2) Determine the state and state variables: express various objective situations when the problem develops to each stage with different states. Of course, the choice of state should meet the requirement of no aftereffect.

(3) Determine the decision and write the state transition equation: because there is a natural connection between decision and state transition, state transition is to derive the state of this stage according to the state and decision of the previous stage. Therefore, if the decision is determined, the state transition equation can be written. But in fact, it is often done in reverse. The decision-making method and state transition equation are determined according to the relationship between the states of two adjacent stages.

(4) Looking for boundary conditions: the given state transition equation is a recursive formula, which requires a recursive termination condition or boundary condition.

P1775 stone consolidation (weakened version)https://www.luogu.com.cn/problem/P1775

Quadrilateral inequality

Large intervals include small intervals. Starting from the smallest interval, they go up the base layer by layer.

#include<bits/stdc++.h>
using namespace std;
int a[310],sum[310],dp[310][310],node[310][310];
///a: Number of stored stones;
//sum: store prefix and;
//dp: record the value after dynamic planning for each interval (the left end point of the first dimension and the right end point of the second dimension);
//node: mark the corresponding separation point (subscript of the optimal separation point) of the minimum value obtained by dynamic programming in each interval 
int n;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=0x3ffffff;//The minimum value is required. First, all are initialized to infinity 
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];//Calculate the prefix sum first to avoid repeated summation later 
		dp[i][i]=0;//There is no additional consumption when not merged. The initial value is 0 
		node[i][i]=i;//For the interval formed by a single node, the optimal separation point is itself 
	}
	for(int len=1;len<=n;len++)//Enumeration length, bottom-up 
	{
		for(int j=1;j+len<=n+1;j++)//Enumerate left endpoints 
		{
			int ends=j+len-1;//Find the position of the right end point 
			for(int i=node[j][ends-1];i<=node[j+1][ends];i++)//For quadrilateral inequality, the optimal separation point must be in this interval 
			{
				if(dp[j][ends]>dp[j][i]+dp[i+1][ends]+sum[ends]-sum[j-1])
				{
					dp[j][ends]=dp[j][i]+dp[i+1][ends]+sum[ends]-sum[j-1];//Update minimum 
					node[j][ends]=i;//Record the corresponding node location 
				}
			}
		}
	}
	cout<<dp[1][n];//Output the results of the top layer 
	return 0;
}

P1880 [NOI1995] stone consolidationhttps://www.luogu.com.cn/problem/P1880 When the chain becomes a ring, the starting point can make any point on the ring. In order to traverse each node in order from each starting point, the ring can be broken into a chain, which only needs to expand the size of the array by one time.

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f

int dp[205][205],dp2[205][205];
//    Min max 
int sum[205];
int node[205][205];//Separation point corresponding to the minimum value 
int num[105];
int main()
{
    int n;
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
	{
        scanf("%d",&num[i]);
        dp[i][i]=0;
        node[i][i]=i;
        sum[i]=sum[i-1]+num[i];
    }
    for(int i=1;i<=n;i++)
	{
        sum[i+n]=sum[i+n-1]+num[i];//Chain extension 
        node[i+n][i+n]=i+n;//Separation point initialization
        dp[i+n][i+n]=0;
    }
    for(int len=2;len<=n;len++)
	{
        for(int j=1;j+len<=2*n;j++)
		{
            int ends = j+len - 1;
            dp2[j][ends]=max(dp2[j+1][ends],dp2[j][ends-1])+sum[ends]-sum[j-1];
            /*Why can the maximum be obtained from the largest of the two endpoints?
			First, the last step can be regarded as the merging of two piles of stones, and the penultimate step can be regarded as the merging of two of the three piles of stones, and then merged with the third pile.
			Which two of the three piles are merged? (w[i] indicates the weight of the ith pile)
			First two piles: w1=2w[1]+2w[2]+w[3]w1=2w[1]+2w[2]+w[3]
			The last two piles: w2=w[1]+2w[2]+2w[3]w2=w[1]+2w[2]+2w[3]
			Therefore, the larger pile in No. 1 and No. 3 should be combined with pile 2, that is, the pile should be combined as large as possible */
        	for(int k = node[j][ends-1];k<=node[j+1][ends];k++)
			{
                if(dp[j][ends]>dp[j][k]+dp[k+1][ends]+sum[ends]-sum[j-1])
                {
                    dp[j][ends]=dp[j][k]+dp[k+1][ends]+sum[ends]-sum[j-1];
                    node[j][ends] = k;
                }
            }
        }
    }
    int ans1 = 0xfffffff,ans2 = -1;
    for(int i=1;i<=n;i++)//Each node on the ring is used as the starting point to form a chain to see which chain has the smallest (largest) result 
	{
        ans1=min(ans1,dp[i][i+n-1]);
        ans2=max(ans2,dp2[i][i+n-1]);
    }
    printf("%d\n%d",ans1,ans2);
    return 0;
}

You can also directly enumerate the separation points between [j,ends).

P2858 [USACO06FEB]Treats for the Cows G/Shttps://www.luogu.com.cn/problem/P2858 You can't be greedy (take out the smaller one at both ends each time), because each decision will affect the subsequent results.

Still consider the smallest interval: when there is only one snack left at the end, it is taken out last, and the initial value needs to be multiplied by the total number of days; Let the snack adjacent to this snack enter this range. It was taken out the day before. The number of days to multiply is reduced by 1, and so on.

#include<bits/stdc++.h> 
using namespace std;
int n,a[2010],dp[2010][2010];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i][i]=a[i]*n;
	}
	for(int len=2;len<=n;len++)
	{
		for(int l=1;l<=n;l++)
		{
			int r=l+len-1;
			if(r>n) break;
			dp[l][r]=max(dp[l+1][r]+a[l]*(n-len+1),dp[l][r-1]+a[r]*(n-len+1));
		}
	}
	cout<<dp[1][n];
	return 0;
}

P1063 [NOIP2006 improvement group] energy Necklacehttps://www.luogu.com.cn/problem/P1063

#include<bits/stdc++.h>
using namespace std;
int a[205],dp[205][205];
int n;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[n+i]=a[i];
	}
	int ans=0;
	for(int len=2;len<=n;len++)//Enumeration interval length 
	{
		for(int i=1;i+len<=2*n;i++)//Enumerate left endpoints 
		{
			int ends=i+len;//Left closed right open section 
			for(int k=i+1;k<ends;k++)//Enumerating separator points 
				dp[i][ends]=max(dp[i][ends],dp[i][k]+dp[k][ends]+a[i]*a[k]*a[ends]);
				//State transition equation: Max (original energy, left interval energy + right interval energy + combined energy)
		}
	}
	for(int i=1;i<=n;i++)
		ans=max(ans,dp[i][n+i]);
	cout<<ans;
	return 0;
}