算法

(DP) $(\mid word1 \mid + \mid word2 \mid)^2$

实际上就是一个有条件限制的最长回文子序列问题。考虑串 $S=word1+word2$，这里的限制条件就是前 $|word1|$ 个字符中至少取一个，且后 $|word2|$ 个字符中至少取一个。

我们首先考虑没有限制条件的最长回文子序列。这是一个经典的动态规划问题，我们有两种做法：

1. 中心扩展，$dp[L][R]$ 表示 $S[L\dots R]$ 范围的最长回文子序列。
2. 令 $T=S’$（$S$ 的倒序），然后求 $S$ 和 $T$ 的最长公共子序列。

考虑引入限制条件。我们使用三个数组，分别记录使用了 $word1$ 的最长回文子序列，使用了 $word2$ 的最长回文子序列和既使用了 $word1$ 又使用了 $word2$ 的最长回文子序列的长度。

在每一次转移时，我们根据当前字符的归属情况（属于 $word1$ 还是 $word2$）来决定是否能进行转移。

需要注意的是，这里我们应该使用上面的方法一（方法二可能也可以，但是会比较复杂），因为方法一中，我们是同时使用了两个字符，可以确保归属情况的正确处理。

C++ 代码

class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        string s = word1 + word2;
        vector<vector<int>> lps1(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps2(n + m + 1, vector<int>(n + m + 1));
        vector<vector<int>> lps12(n + m + 1, vector<int>(n + m + 1));
        for (int len = 1; len <= n + m; ++len)
            for (int l = 1; l + len - 1 <= n + m; ++l) {
                int r = l + len - 1;
                bool use1 = l <= n;
                bool use2 = r > n;
                if (len == 1) {
                    if (use1)
                        lps1[l][l] = 1;
                    if (use2)
                        lps2[l][l] = 1;
                    continue;
                }
                if (s[l - 1] == s[r - 1]) {
                    if (use1 && use2) {
                        lps12[l][r] = lps12[l + 1][r - 1] + 2;
                    }
                    if (use1) {
                        if (lps2[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps2[l + 1][r - 1] + 2);
                        lps1[l][r] = lps1[l + 1][r - 1] + 2;
                    }
                    if (use2) {
                        if (lps1[l + 1][r - 1] > 0)
                            lps12[l][r] = max(lps12[l][r], lps1[l + 1][r - 1] + 2);
                        lps2[l][r] = lps2[l + 1][r - 1] + 2;
                    }
                }
                lps12[l][r] = max(lps12[l][r], max(lps12[l + 1][r], lps12[l][r - 1]));
                lps1[l][r] = max(lps1[l][r], max(lps1[l + 1][r], lps1[l][r - 1]));
                lps2[l][r] = max(lps2[l][r], max(lps2[l + 1][r], lps2[l][r - 1]));
        }
        return lps12[1][n + m];
    }
};