Introduction to interval DP

    Section dp, seeing the name of a thing one thinks of its function , On the interval dp, The state of most topics is determined by the interval （ Be similar to dp[l][r] This form ） Composed of , That is, we can convert large areas into small areas for processing , Then, after the inter cell processing, the value of the large interval can be obtained by backtracking , There are two main methods , Memory search and recursion .

When using recursion to solve , The key is that recursion is for The sequence in the loop , as well as dp The key to ： State transition equation .

Of course, most of the intervals dp They all have their own characteristics , We can consider under what conditions , Large intervals can be transformed into small intervals , Then find out the boundary conditions , Conduct dp solve .

Example 1： Stone merging （ Can form a ring ）

Problem Description
Around a circular playground N Rubble （N≤300）, Now we need to combine the stones into a pile in order . It is stipulated that only two adjacent piles can be selected at a time to merge into a new pile , And count the new pile of stones , Record as the score of the merger . Make a program , Number of heaps read from file N And the number of stones in each pile （≤２０）, Choose a plan to merge stones , Make do N－1 The merger , The sum of the scores is the smallest ;

for example , Shown ４ Rubble , Number of stones per pile （ Count from the top pile , Number of punctures in time ） In turn ４５９４. be ３ The scheme with the smallest sum of sub combined scores ：８＋１３＋２２＝４３

Input
The first line is the number of stone piles N;
The second line is the number of stones in each pile , Every two numbers are separated by a space character .

Output
The sum of combined scores is the smallest

SampleInput
4
4 5 9 4
SampleOutput
43

#include<bits/stdc++.h>
using namespace std;
const int N=605;
const int INF=0x3f3f3f3f;
int a[N]={
    0};
int sum[N]; //  Record prefix and 
int dp[N][N];  //  Express i->j The minimum value of 
int main() {
    
    memset(dp,0,sizeof(dp)); // initialization 
	int n;
	cin >> n;
	for(int i=1;i<=n;i++) {
    
		cin >> a[i];
		a[i+n]=a[i]; // Because it's circular , So set a[i] The total length of 2n
	}
	for(int i=1;i<=2*n;i++)
		sum[i] = sum[i-1] + a[i]; // The prefix and 
	for(int dist=2;dist<=n;dist++) {
      // Interval length 
		for(int start=1;start<=2*n-dist+1;start++) {
      // The starting point 
			int end = start+dist-1;  // End 
			
			dp[start][end] = INF; 
			for(int k=start;k<end;k++) {
     // In the middle 
				dp[start][end] = min(dp[start][end],dp[start][k]+dp[k+1][end]+sum[end]-sum[start-1]);
			
			}
		}
	}
	int ans=INF;
	for(int i=1;i<=n;i++)
		ans=min(ans,dp[i][i+n-1]);
	cout << ans << endl;
	
	return 0;
}

Example 2： Parentheses matching

We give the following inductive definition of a “regular brackets” sequence: the empty sequence is a regular brackets sequence, if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and if a and b are regular brackets sequences, then ab is a regular brackets sequence. no other sequence is a regular brackets sequence For instance, all of the following character sequences are regular brackets sequences: (), [], (()), ()[], ()[()] while the following character sequences are not: (, ], )(, ([)], ([(] Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence. Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

SampleInput
((()))
()()()
([]])
)[)(
([][][)
end
SampleOutput
6
6
4
0
6

Code ：

#include<iostream>
#include<cstring>
using namespace std;
const int N=305;
const int INF=0x3f3f3f3f;
char a[N];
int dp[N][N];
int main() {
    
	while(cin >> a+1) {
    
        if(a[1] == 'e')break;
        memset(dp,0,sizeof(dp));
        int n =strlen(a+1);
        for(int len=2;len<=n;len++) {
    
            for(int start=1;start<=n-len+1;start++) {
    
                int end = start + len -1;
                if(end>n)break;
                if(a[start]=='('&&a[end]==')' || a[start]=='['&&a[end]==']')
                    dp[start][end] = dp[start+1][end-1] + 2;
                
                for(int k=start;k<end;k++) {
    
                    dp[start][end] = max(dp[start][end],dp[start][k]+dp[k+1][end]);
                }
            }
        }
        cout << dp[1][n] << endl;
    }

	return 0;
}

Time complexity O(n^3), about n Greater than 1000 May time out when , Quadrilateral inequality can be used for optimization , Reference resources ： Quadrilateral inequality optimization