DP - Codeforces Problem 1506C - Double-ended Strings

#include <bits/stdc++.h>
using namespace std;
const int N = 20+5;
int t;
int inf;
int maxlen;
int m, n;
char a[N], b[N];
int dp[N][N][N];
// dp[i][j][v] 表示a从i开始,b从j开始, 长度为v的两串相同, 所需耗费的最小删除次数
int main(){
	scanf("%d", &t);
	while(t--){
		scanf("%s%s", a+1, b+1);
		m = strlen(a+1);
		n = strlen(b+1);
		maxlen = min(m, n);
		inf = m+n;
		for(int i = 1; i <= m; ++i){
			for(int j = 1; j <= n; ++j){
				for(int v = 0; v <= maxlen; ++v){
					dp[i][j][v] = inf;
				}
			}
		}
		
		for(int i = 1; i <= m; ++i){
			for(int j = 1; j <= n; ++j){
				if(a[i] == b[j]){
					dp[i][j][1] = inf-2;
				}
			}
		}
		
		for(int v = 2; v <= maxlen; ++v){
			for(int i = 1; i + v - 1 <= m; ++i){
				for(int j = 1; j + v - 1 <= n; ++j){
					if(a[i+v-1] == b[j+v-1])
						dp[i][j][v] = dp[i][j][v-1] - 2;
				}
			}
		}
		
		
		int ans = inf;
		for(int i = 1; i <= m; ++i){
			for(int j = 1; j <= n; ++j){
				for(int v = 0; v <= maxlen; ++v){
					ans = min(ans, dp[i][j][v]);
				}
			}
		}
		
		printf("%d\n", ans);
	}
	return 0;
}

DP - Codeforces Problem 1506C - Double-ended Strings

原文：https://www.cnblogs.com/popodynasty/p/14635642.html