dp

首先将word1和word2拼接起来

状态表示及转移

$f[i][j]:[i,j]中最长回文子序列长度$
最长回文子序列模板
$f$数组存满足$i \leq word1.size()-1$且$j \geq word1.size()$且$w[i]==w[j]$的状态转移

$f1$辅助数组存所有情况下的最长回文自序列

class Solution {
public:
    int f[2010][2010],f1[2010][2010];
    int longestPalindrome(string w1, string w2) {
        return dp(w1,w2);
    }
    int dp(string w1,string w2)
    {
        memset(f,0,sizeof f);
        string w = w1+w2;
        int n=w.size(),n1=w1.size(),n2=w2.size(),res=0;
        for(int i=0;i<n;i++)f[i][i]=1;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(j-i+1>2)
                {

                    if(w[i]==w[j])
                    {
                        if(i<n1 && j>=n1)
                            f[i][j]=max(f[i][j],max(f[i+1][j-1]+2,f1[i+1][j-1]+2));
                        f1[i][j]=max(f1[i][j],f1[i+1][j-1]+2);
                    }

                    if(i<n1 && j>=n1)    
                        f[i][j]=max(f[i][j],max(f[i+1][j],f[i][j-1]));
                    f1[i][j]=max(f1[i][j],max(f1[i+1][j],f1[i][j-1]));
                }
                else
                {
                    if(i<n1 && j>=n1)
                        f[i][j]=w[i]==w[j]?j-i+1:1;
                    f1[i][j]=w[i]==w[j]?j-i+1:1;
                }
            }
        }
        return f[0][n-1]==1?0:f[0][n-1];
    }
};