解题思路

在思考这一问题之前可以尝试解决******问题。
我们使用区间DP来解决这一问题。
用F(l1,r1,l2,r2)表示如下含义：
    a字符串中的子串(a_{l1},a_{r1})以及b字符串中的子串(b_{l2},b_{r2})能否构成回文字符串。
每个状态只有0和1，可以考虑使用或运算。
于是开始推导状态转移：
  • F(l1,r1,l2,r2)|=F(l1+1,r1-1,l2,r2)\ ,a_{l1}=a_{r1}
  • F(l1,r1,l2,r2)|=F(l1+1,r1,l2,r2-1)\ ,a_{l1}=b_{r2}
  • F(l1,r1,l2,r2)|=F(l1,r1-1,l2+1,r2)\ ,b_{l2}=a_{r1}
  • F(l1,r1,l2,r2)|=F(l1,r1,l2+1,r2-1)\ ,b_{l2}=b_{r2}
边界条件：两个字符串中最多选出一个字符时，F(l1,r1,l2,r2)=1 

代码 

int dp[55][55][55][55];
void solve() {
    string a, b;
    cin >> a >> b;
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    int n = a.size(), m = b.size();
    for (int len1 = 0;len1 <= n;len1++)
        for (int len2 = 0;len2 <= m;len2++)
            for (int l1 = 1;l1 <= n - len1 + 1;l1++)
                for (int l2 = 1;l2 <= m - len2 + 1;l2++) {
                    int r1 = l1 + len1 - 1, r2 = l2 + len2 - 1;
                    if (len1 + len2 < 2) dp[l1][r1][l2][r2] = 1;
                    else {
                        if (r1 >= 1 && a[l1 - 1] == a[r1 - 1]) dp[l1][r1][l2][r2] |= dp[l1 + 1][r1 - 1][l2][r2];
                        if (r2 >= 1 && b[l2 - 1] == b[r2 - 1]) dp[l1][r1][l2][r2] |= dp[l1][r1][l2 + 1][r2 - 1];

                        if (r2 >= 1 && a[l1 - 1] == b[r2 - 1]) dp[l1][r1][l2][r2] |= dp[l1 + 1][r1][l2][r2 - 1];
                        if (r1 >= 1 && b[l2 - 1] == a[r1 - 1]) dp[l1][r1][l2][r2] |= dp[l1][r1 - 1][l2 + 1][r2];
                    }

                    if (dp[l1][r1][l2][r2]) ans = max(ans, len1 + len2);
                }
    cout << ans << endl;
    return;
}