涉及知识点：

区间dp

solution：

划重点：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

大多数区间dp的模板都长这样子：

for(int len = 1; len <= n; len++){
    for(int j =1; j + len <= n+1; j++){
        int ends = j + len - 1;
        for(int i = j; i < ends; i++){
            dp[j][lens] = min(dp[j][lens] , dp[j][i] + dp[i+1][ends] + something);
        }
    }
}

接下来分三步求解这道题目：

• 第一步，设dp[i][j][k][z]表示a[i....j]和b[k.....z]合并是否能组成回文串
• 第二步，处理初始化，显然当(j-i) + (z-k) 小于等于1，dp[i][j][k][z] = 1
• 第三步，转移方程:

  //回文串最左边的字符a[i]和最右边的字符a[j]相等
  dp[i][j][k][z] |= dp[i+1][j-1][k][z];
  //回文串最左边的字符b[k]和最右边的字符b[z]相等
  dp[i][j][k][z] |= dp[i][j][k+1][z-1];
  //回文串最左边的字符a[i]和最右边的字符b[z]相等
  dp[i][j][k][z] |= dp[i+1][j][k][z-1];
  //回文串最左边的字符b[k]和最右边的字符a[j]相等
  dp[i][j][k][z] |= dp[i][j-1][k+1][z];

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 55;
int dp[maxn][maxn][maxn][maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string a,b;
        cin>>a>>b;
        int ans = 0;
        for(int l1=0;l1<=a.length();l1++){
            for(int l2=0;l2<=b.length();l2++){
                for(int i=1,j=l1;j<=a.length();i++,j++){
                    for(int k=1,z=l2;z<=b.length();k++,z++){
                        if(l1 + l2 <= 1)
                            dp[i][j][k][z] = 1;
                        else{
                            dp[i][j][k][z] = 0;
                            if(a[i-1] == a[j-1] && l1 > 1)
                                dp[i][j][k][z] |= dp[i+1][j-1][k][z];
                            if(b[k-1] == b[z-1] && l2 > 1)
                                dp[i][j][k][z] |= dp[i][j][k+1][z-1];
                            if(a[i-1] == b[z-1] && l1 && l2)
                                dp[i][j][k][z] |= dp[i+1][j][k][z-1];
                            if(a[j-1] == b[k-1] && l1 && l2)
                                dp[i][j][k][z] |= dp[i][j-1][k+1][z];
                        }
                        if(dp[i][j][k][z])
                            ans = max(ans , l1 + l2);
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return  0;
}