Linear DP (basic questions have been updated)

Today is Friday , It's a bit of a mess , Just write a little , Study hard tomorrow ！

Digital triangle

Basic is dp Of hello world The topic is , Review the

/*  State means ： dp[i][j] Indicates all paths to （i,j） The maximum of the sum of numbers   State transition equation ：  The maximum value of a certain point may come from the upper left or right , Just compare these two   Considering the storage position of numbers in the array , We get the following state transition equation  dp[i][j]=max(dp[i-1][j]+g[i][j],dp[i-1][j+1]+g[i][j]) */


#include<iostream>

using namespace std;

const int N=600;

int inf=1e9;
int g[N][N];
int dp[N][N];

int main(){
    
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			cin>>g[i][j];
	
	for(int i=0;i<=n;i++)
		for(int j=0;j<=i+1;j++)
			dp[i][j]=-inf;
	
	// This part is for the rightmost part of each line , Prevent it from adding and an empty （0） Compare （ Because there is only one way to go on the far right ） 
	// The data may be wrong , But add a very small  （ Originally empty ） Then the comparison will definitely get the value with path  
	// Please enlarge the scope here , And then you need to [1][1] Assign initial value to  
	dp[1][1]=g[1][1];
	
	for(int i=2;i<=n;i++)
		for(int j=1;j<=i;j++)
			dp[i][j]=max(dp[i-1][j]+g[i][j],dp[i-1][j-1]+g[i][j]);
			
	int ans=-inf;
	for(int i=1;i<=n;i++)
		if(dp[n][i]>ans)
			ans=dp[n][i];
	cout<<ans<<endl;
	return 0;
}

Longest ascending subsequence

Topic linking

Subsequence is not a substring , It can't be adjacent , As long as the order is right

/*
 Longest ascending subsequence  


 State means  
dp[i] Says to the first i The length of the longest ascending subsequence at the end of the number 

 State transition equation 
dp[i] in , We think dp[i] Represents the longest ascending subsequence , Because in order to a[i] ending , therefore a[i] The first number may be a[1],a[2]..a[i-1] One of them 
 So we need to find a[i] The end is long , Just look at the longest one in front dp[j]((j<i) also a[j]<a[i]( Strictly increasing ))
 Then take the largest one  

*/

#include<iostream>

using namespace std;

const int N=2000;

int n;
int a[N];
int dp[N]; 
 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	
	for(int i=1;i<=n;i++)
		dp[i]=1; 
	// Note that initialization is required here , Because the minimum value of the longest ascending subsequence ending with each element is 1	
		
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i-1;j++){
			if(a[j]<a[i]){
				dp[i]=max(dp[i],dp[j]+1);
			}	
		}
	}
	
	int ans=dp[1];
	
	for(int i=1;i<=n;i++)
		if(dp[i]>ans)
			ans=dp[i];
	cout<<ans<<endl;
	return 0;
}

Longest ascending subsequence 2

Topic link

For the optimization of the previous method

/*  Optimized version of the longest ascending subsequence ：  The time complexity of previous versions is O(n^2)  This version uses binary , The time complexity is O(nlogn)  The specific ideas are ：  Suppose you give a sequence ：3,1,5,6  If you follow the previous method , With a[1]=3,a[2]=1 The longest ending is 1, Then when you inherit later ,  These two positions are equivalent , however ！1 Than 3 Small ！ Can be placed in 3 The back one can be put in 1 Back ,  But it can be put in 1 hinder 2 Can't put 3 Back , This shows that in fact 3 It's useless. , Then judge according to the original method ,  It's a waste of time , So the way to consider is to create an array q, Used to record the minimum value of elements under each length   namely q[len]=a[k](a[k] For all lengths len The minimum value of the last element of the subsequence of )  So for a a[i], What we need to do is to see which one it can put q[len] Back , Because of the above thought ,  We try to find q[len] maximal , This can put the most   So now it's time to compare a[i] The small and the largest q[len], Use two points , But it needs to be proved q The monotonicity of   The following proof q[len] Is strictly monotonically increasing   Using the method of disproportion   Yes q[len-1] and q[len]  hypothesis ：q[len]<=q[len-1]  because q The length of the subsequence in is len The minimum value of the end element of , that q[len]>k(k For len-1 Some last element at the end )  Because of the assumption that q[len]<=q[len-1], therefore k<q[len-1], that k Is the length len-1 The minimum value at the end of   contradiction , So the hypothesis doesn't hold   therefore q Is strictly monotonically increasing   In fact, this idea is similar to greed  */


#include<iostream>

using namespace std;

const int N=1e6;

int a[N];
int q[N];


int main(){
    
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
		

	
	int len=0;
	for(int i=1;i<=n;i++){
    
		int l=0,r=len;
		while(l<r){
    
			int mid =(r+l+1)/2;
			if(q[mid]<a[i])
				l=mid;
			else
				r=mid-1;
		}
		// The largest ratio can be divided in two a[i] Small number  
		// It means a[i] Can be placed in q[mid] Back , But it can't make len Getting bigger still needs comparison 
		len=max(len,r+1);
		// You can put it directly , Because it's binary 
		// therefore q[r]<a[i]<q[r+1]
		// So you can update q[r+1] by a[i] 
		q[r+1]=a[i]; 
	}
	cout<<len<<endl;
	return 0;
}

Maximum common subsequence

Topic link

/*  Given two lengths, they are  N  and  M  String  A  and  B  Seeking both  A  The subsequence of is  B  What is the longest string length of the subsequence of .  Input format   The first line contains two integers  N  and  M.  The second line contains a length of  N  String , Representation string  A.  The third line contains a length of  M  String , Representation string  B.  Strings are made up of lowercase letters . */


/*  Be careful ： Here is the public sequence , Not substring , Not necessarily adjacent   One 、 State means  dp[i][j] Express a Before i and b Before j A set of common sequences  dp[i][j] The value of is the maximum length of these common sequences   Two 、 State transition equation   For a dp[i][j], We need to divide   By the end of a[i] And the b[j] Elements   Four situations : a[i] Packages are not included in the longest common sequence (0,1) b[j] Packages are not included in the longest common sequence (0,1) 1. 00 dp[i][j]=dp[i-1][j-1] #2 and 3 Want to review the online class  2. 01 dp[i-1][j] 3. 10 dp[i][j-1] 4. 11  Satisfy a[i]=b[j] dp[i][j]=dp[i-1][j-1]+1 */


#include<iostream>

using namespace std;

const int Num=2000;
int N,M;
char a[Num],b[Num];
int dp[Num][Num];

int main(){
    
	cin>>N>>M;
	getchar();
	for(int i=1;i<=N;i++)
		scanf("%c",&a[i]);
	getchar();
	for(int i=1;i<=M;i++)
		scanf("%c",&b[i]);	
	
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++){
    
			if(a[i]==b[j])
				dp[i][j]=dp[i-1][j-1]+1;
			else
				dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]));
		}
	cout<<dp[N][M]<<endl;
	return 0;
}

The shortest editing distance

subject

Topic linking

Code

/*  The shortest editing distance ：  A problem that seems impossible to start , Use dp  State means ：  Similar to the largest common subsequence written yesterday  dp[i][j] It means that you will A Before i Convert characters into B Before j A collection of operations   We use dp[i][j] It means that you will A Before i Convert characters into B Before j The minimum number of operands required   State transition equation ：  One 、 Delete   If delete , that a Before i-1 You want and b Before j An equal  dp[i][j]=dp[i-1][j]+1  Two 、 Insert  dp[i][j]=dp[i][j-1]+1  3、 ... and 、 Replace   Replacement only requires both sides before i-1 and j-1 An equal  dp[i][j]=dp[i-1][j-1]+1 (dp[i][j] It can't be better than dp[i][j-1] It's still small ) */	
	
	
#include<iostream>
	
using namespace std;
int n,m;
	
const int N=1100;
	
int a[N],b[N];
int dp[N][N]; 
	
int main(){
    
	cin>>n;
	getchar();
	for(int i=1;i<=n;i++)
		scanf("%c",&a[i]);
	
	getchar();
	cin>>m;
	getchar();
	for(int i=1;i<=m;i++)
		scanf("%c",&b[i]);
	
	
	for(int i=0;i<=n;i++)
		dp[i][0]=i;// hold a Before i Characters and b Before 0 It takes i operations 
		
	for(int j=0;j<=m;j++)
		dp[0][j]=j; 
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
    
			if(a[i]==b[j])
				dp[i][j]=dp[i-1][j-1];
			else
				dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));		
	}
	
	cout<<dp[n][m]<<endl;	
	return 0;
}	

Edit distance

subject

Topic linking

Code

#include<iostream>
#include<string.h>

using namespace std;

int n,m,t;

const int N=2000;
const int M=20;

char a[N][N];
char b[N];




int main(){
    
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%s",a[i]);
	for(int i=1;i<=n;i++){
    
		// Translate all strings backward by one position  
		int m=strlen(a[i]);
		for(int j=m-1;j>=0;j--){
    
			a[i][j+1]=a[i][j];	
		}	
	}
	for(int j=1;j<=m;j++){
    
		scanf("%s",b);
		int tmp_b=strlen(b);
		for(int q=tmp_b-1;q>=0;q--)
			b[q+1]=b[q];	
		cin>>t;
		int ans=0;
		int lenb=tmp_b;
		for(int i=1;i<=n;i++){
    
			// This part will a[i] and b Compare  
			int lena=strlen(a[i])-1;
			int dp[M][M];
			for(int j=0;j<=lena;j++)
				dp[j][0]=j;
			for(int j=0;j<=lenb;j++)
				dp[0][j]=j;
			for(int x=1;x<=lena;x++){
    
				for(int y=1;y<=lenb;y++){
    
					if(a[i][x]==b[y])
						dp[x][y]=dp[x-1][y-1];
					else
						dp[x][y]=min(min(dp[x][y-1]+1,dp[x-1][y]+1),dp[x-1][y-1]+1);
				}
			} 
			if(dp[lena][lenb]<=t)
				ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}