class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        N, n1, n2 = len(s), len(word1), len(word2)
        dp = [[0] * N for _ in range(N)]
        ans = 2 if word1[-1] == word2[0] else 0
        # 对角线必为1，i < j为0
        for i in range(N):
            dp[i][i] = 1
        # 从下往上遍历
        for i in range(N - 1, -1, -1):
            for j in range(i + 1, N, 1):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                    if i < n1 and j >= n1:
                        ans = max(ans,dp[i][j])
                else:
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])
                
        return ans

动态规划 困难 把两个序列拼在一起，这题就变成了 0516.最长回文子序列

https://leetcode-cn.com/problems/longest-palindromic-subsequence/