双序列动态规划

状态定义

往往是$f[n][m]$的二维状态，$n,m$为两个序列的长度

状态转移

往往是与$f[i][j-1]$,$f[i-1][j]$,$f[i-1][j-1]$有关

例

P1140

$f[i][j]$表示A串$[0,i]$匹配B串$[0,j]$所得最大价值

正解

$f[i][j]=max(f[i][j-1]+table[b[j]]['-'],f[i-1][j]+table[a[i]]['-'],f[i-1][j-1]+table[a[i]][b[j]])$

暴力

若$b[j]$与A串匹配$f[i][j]=max(f[k-1][j-1]+table[a[k]][b[j]]+sum[i]-sum[k])$

否则与空串$f[i][j]=f[i][j-1]+table[b[j]]['-']$

其中$sum[i]$表示A串与空串匹配价值的前缀和

求解目标$f[n][m]$

for(int i=1;i<=n;i++){
	sum[i]=sum[i-1]+t[g(a[i])][g('-')];
}
f[0][0]=0;
for(int i=1;i<=m;i++){
	f[0][i]=f[0][i-1]+t[g(b[i])][g('-')];
	f[i][0]=f[i-1][0]+t[g(a[i])][g('-')];
}
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		/*
		f[i][j]=f[i][j-1]+t[g(b[j])][g('-')];
		for(int k=i;k;k--){
			f[i][j]=max(f[i][j],f[k-1][j-1]+t[g(a[k])][g(b[j])]+sum[i]-sum[k]);
		}
		*/
		f[i][j]=max(f[i-1][j-1]+t[g(a[i])][g(b[j])],max(f[i-1][j]+t[g(a[i])][g('-')],f[i][j-1]+t[g(b[j])][g('-')]));
	}
}

P1439

$f[i][j]$表示A串$[0,i]$和B串$[0,j]$的最长公共子序列的长度

如果$a[i]==b[j],f[i][j]=f[i-1][j-1]+1$

否则$f[i][j]=max(f[i-1][j],f[i][j-1])$

求解目标$f[n][m]$

P2758

$f[i][j]$表示将A串$[0,i]$转化为B串$[0,j]$的最小代价

如果$a[i]==b[j],f[i][j]=f[i-1][j-1]$

否则$f[i][j]=min(f[i][j-1],f[i-1][j],f[i-1][j-1])+1$

求解目标$f[n][m]$

for(int i=0;i<=n;i++)f[i][0]=i;
for(int i=0;i<=m;i++)f[0][i]=i;
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		f[i][j]=min(f[i][j],f[i-1][j]+1);
		f[i][j]=min(f[i][j],f[i][j-1]+1);
		f[i][j]=min(f[i][j],f[i-1][j-1]+1);
		if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
	}
}

P2679

$f[i][j][k]$表示从A串$[0,i]$中取出k个不重叠子串顺次连接，所形成的新字符串与B串$[0,j]$相等

若不选$a[i]$，$f[i][j][k]=f[i-1][j][k]$

若选$a[i]$,$f[i][j][k]=Sum(f[i-t][j-t][k-1])$

所以$f[i][j][k]=f[i-1][j][k]+Sum(f[i-t][j-t][k-1])$

优化:

令$sum[i][j][k]=Sum(f[i-t][j-t][k-1])$

显然，若$a[i]==b[j]$,$sum[i][j][k]=sum[i-1][j-1][k]+f[i-1][j-1][k-1]$

否则$sum[i][j][k]=0$

省略第一维

求解目标$f[m][K]$

注意取模

for(int i=0;i<=n;i++){
	f[0][0]=1;
}
for(int i=1;i<=n;i++){
	for(int j=m;j>=1;j--){
		for(int k=K;k>=1;k--){
			if(a[i]==b[j])sum[j][k]=(sum[j-1][k]+f[j-1][k-1])%mod;
			else sum[j][k]=0;
			f[j][k]=(f[j][k]+sum[j][k])%mod;
		}
	}
}