传送门 递推方程也很容易找到：
if (s1[i] == s1[j]) dp[i][j][k][l] |= dp[i+1][j-1][k][l]; if (s2[k] == s2[l]) dp[i][j][k][l] |= dp[i][j][k+1][l-1]; if (s1[j] == s2[k]) dp[i][j][k][l] |= dp[i][j-1][k+1][l]; if (s1[i] == s2[l]) dp[i][j][k][l] |= dp[i+1][j][k][l-1];首先枚举长度，必须从0开始。是因为可能一个为空，一个不为空的情况。 基本可以写出代码：
#include <iostream> #include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <deque> #include <cstdlib> #define lowbit(x) ((x) & -(x)) #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 const int maxn = 2e6 + 7; const int INF = 0x3f3f3f3f; typedef long long ll; using namespace std; const ll mod = 1e9 + 7; const double pi = acos(-1.0); inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = (x<<1) + (x<<3) + (ch^48); ch = getchar(); } return x * f; } int dp[53][52][52][52]; int main(){ //ios::sync_with_stdio(false); // freopen("text.txt","r",stdin); // freopen("out1.txt","w",stdout); int t; string s1, s2; cin >> t; while(t --){ memset(dp,0,sizeof(dp)); int ans = 0; cin >> s1 >> s2; int len1 = s1.size(); int len2 = s2.size(); for (int x = 0; x <= len1; x ++){ for (int y = 0; y <= len2; y ++){ for (int i = 0; i + x < len1; i ++){ for (int k = 0; k + y < len2; k ++){ int j = i + x - 1; int l = k + y - 1; if (x + y <= 1) dp[i][j][k][l] = 1; else{ if (s1[i] == s1[j] && x > 1) dp[i][j][k][l] |= dp[i+1][j-1][k][l]; if (s2[k] == s2[l] && y > 1) dp[i][j][k][l] |= dp[i][j][k+1][l-1]; if (s1[j] == s2[k] && x && y) dp[i][j][k][l] |= dp[i][j-1][k+1][l]; if (s1[i] == s2[l] && x && y) dp[i][j][k][l] |= dp[i+1][j][k][l-1]; } if (dp[i][j][k][l]) ans = max(ans,x+y); } } } } cout << ans << endl; } return 0; }但是，这个是错的，会导致数组越界。出现下标为-1的情况。因此大部分人的做法是从s[1]开始存，到s[len]，这样就有效的避免了数组越界。也有大佬没有那样写，但没说明情况，很可能导致一些人看不懂。所以我考虑dp的下标全部加1，这样就不会越界了。
#include <iostream> #include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <deque> #include <cstdlib> #define lowbit(x) ((x) & -(x)) #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 const int maxn = 2e6 + 7; const int INF = 0x3f3f3f3f; typedef long long ll; using namespace std; const ll mod = 1e9 + 7; const double pi = acos(-1.0); inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = (x<<1) + (x<<3) + (ch^48); ch = getchar(); } return x * f; } int dp[53][53][53][53]; int main(){ //ios::sync_with_stdio(false); // freopen("text.txt","r",stdin); // freopen("out1.txt","w",stdout); int t; string s1, s2; cin >> t; while(t --){ memset(dp,0,sizeof(dp)); int ans = 0; cin >> s1 >> s2; int len1 = s1.size(); int len2 = s2.size(); for (int x = 0; x <= len1; x ++){ for (int y = 0; y <= len2; y ++){ for (int i = 0; i + x - 1 < len1; i ++){ for (int k = 0; k + y - 1 < len2; k ++){ int j = i + x - 1; int l = k + y - 1; if (x + y <= 1) dp[i+1][j+1][k+1][l+1] = 1; else{ if (s1[i] == s1[j] && x > 1) dp[i+1][j+1][k+1][l+1] |= dp[i+2][j][k+1][l+1]; if (s2[k] == s2[l] && y > 1) dp[i+1][j+1][k+1][l+1] |= dp[i+1][j+1][k+2][l]; if (s1[j] == s2[k] && x && y) dp[i+1][j+1][k+1][l+1] |= dp[i+1][j][k+2][l+1]; if (s1[i] == s2[l] && x && y) dp[i+1][j+1][k+1][l+1] |= dp[i+2][j+1][k+1][l]; } if (dp[i+1][j+1][k+1][l+1]) ans = max(ans,x+y); } } } } cout << ans << endl; } return 0; }