题解 | #合并回文子串#

区间DP问题。与涂色问题大同小异，但如果想不明白就会觉得这两者有很大区别。

用一个四维数组dp[l1][r1][l2][r2]表示从第一个字符串中取l1到r1，从第二个字符串中取l2到r2是否能组成回文字符串，若不能则为0，能则为1。
状态转移方程分4种情况，因为字符串Ａ、Ｂ有四种情况可以组成会问字符串。第一种是A在左B在右，直接拼接，若其能组成回文字符串，则有A[l1]==B[r2]，此时有状态转移方程dp[l1][r1][l2][r2]|=dp[l1+1][r1][l2][r2-1]；第二种是B在左，A在右，直接拼接，则有A[r1]==B[l2]，此时有状态转移方程dp[l1][r1][l2][r2]|=dp[l1][r1-1][l2+1][r2]；第三种情况是B插入A内部，A包住B，则有A[l1]==A[r1]，此时有状态转移方程dp[l1][r1][l2][r2]|=dp[l1+1][r1-1][l2][r2];第四种情况是A插入B内部，B包住A，则有B[l2]==B[r2]，此时有状态转移方程dp[l1][r1][l2][r2]|=dp[l1][r1][l2+1][r2-1]。
在循环迭代时要使用四重循环，外部两重控制A、B两个字符串取子串的长度，内部两重控制A、B两个字符串取子串的起点。四重循环就可以唯一决定取出的两个子串，再判断这两个子串是否能组成一个回文子串即可。
关于dp数组的初始状态，当仅选中一个字符或不选择字符时，认为它是回文的，所以在遍历中遇到未选择字符或仅选一个字符的情况，为其赋1。
关于判断的条件限制问题，要理解四种判断对应的情况，当情况是A包住B时，那么A的长度至少要为2，同理判断B包住A时B的长度至少为2。当情况是A左B右或B左A右时，A与B的长度都至少要为1。

另外有个下标的小坑，这里为了保证迭代过程中不发生越界，使数组的大小比数据范围的大小大了2，即n=n+2，这是为了应对在边界-1或+1时发生越界。这就使得l1r1在dp数组中表示A字符串中第l1个字符到第r1个字符。而在A数组中并没有做类似得扩容处理，所以A字符串中第l1个字符在A数组中为A[l1-1]，第r1个字符为A[r1-1]。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){
    int T;
    cin >> T;
    for(int i = 0;i < T;i++){
        string A, B;
        cin >> A >> B;
        int n1 = A.size();
        int n2 = B.size();
        vector<int> temp1(n2 + 2, 0);
        vector<vector<int>> temp2(n2 + 2, temp1);
        vector<vector<vector<int>>> temp3(n1 + 2, temp2);
        vector<vector<vector<vector<int>>>> dp(n1 + 2, temp3);
        int res = 1;
        for(int step1 = 0;step1 <= n1;step1++){
            for(int step2 = 0;step2 <= n2;step2++){
                for(int l1 = 1;step1 + l1 - 1 <= n1;l1++){
                    for(int l2 = 1;step2 + l2 - 1 <= n2;l2++){
                        int r1 = step1 + l1 - 1;
                        int r2  = step2 + l2 - 1;
                        if(step1 + step2 <= 1){
                            dp[l1][r1][l2][r2] = 1;
                        }
                        else{
                            if(A[l1 - 1] == A[r1 - 1] && step1 > 1){
                                dp[l1][r1][l2][r2] |= dp[l1 + 1][r1 - 1][l2][r2];
                            }
                            if(A[l1 - 1] == B[r2 - 1] && step1 && step2){
                                dp[l1][r1][l2][r2] |= dp[l1 + 1][r1][l2][r2 - 1];
                            }
                            if(A[r1 - 1] == B[l2 - 1] && step1 && step2){
                                dp[l1][r1][l2][r2] |= dp[l1][r1 - 1][l2 + 1][r2];
                            }
                            if(B[l2 - 1] == B[r2 - 1] && step2 > 1){
                                dp[l1][r1][l2][r2] |= dp[l1][r1][l2 + 1][r2 - 1];
                            }
                            if(dp[l1][r1][l2][r2]){
                                res = max(res, step1 + step2);
                            }
                        }
                    }
                }
            }
        }
        cout << res <<endl;
    }
}