合并回文子串

题解:
假设a[i][j]与b[k][l]可以构成,那么就是可以得到:
dp[i][j][k][l]表示上述状态,然后根据回文性质推出

上图转载自:https://blog.csdn.net/weixin_39909619/article/details/90256332
时间复杂度:四个for,.....O(N^4)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;
int dp[maxn][maxn][maxn][maxn];

int main()
{
    int i, j, k, m, n, T;
    cin >> T;
    string a, b;
    while (T--)
    {
        int ans = 0;
        cin >> a >> b;
        for (int da = 0; da <= a.size(); ++da)
            for (int db = 0; db <= b.size(); ++db)
                for (int i = 0; da + i <= a.size(); ++i)
                    for (int j = 0; db + j <= b.size(); ++j)
                    {
                        if (da + db <= 1)
                            dp[i][i + da][j][j + db] = 1;
                        else
                        {
                            dp[i][i + da][j][j + db] = 0;  
                            if (da >= 2 && a[i] == a[i + da - 1])
                                dp[i][i + da][j][j + db] |= dp[i + 1][i + da - 1][j][j + db];
                            if (db >= 2 && b[j] == b[j + db - 1])
                                dp[i][i + da][j][j + db] |= dp[i][i + da][j + 1][j + db - 1];
                            if (db >= 1 && da >= 1 && a[i] == b[j + db - 1])
                                dp[i][i + da][j][j + db] |= dp[i + 1][i + da][j][j + db - 1];
                            if (db >= 1 && da >= 1 && b[j] == a[i + da - 1])
                                dp[i][i + da][j][j + db] |= dp[i][i + da - 1][j + 1][j + db];
                        }
                        if (dp[i][i + da][j][j + db])ans = max(ans, da + db);
                    }
        cout << ans << endl;
    }
    return 0;
}