problem:1771. 由子序列构造的最长回文串的长度

思路：最长回文子序列升级版，题目要求选取的子序列不能为空，所以可以在求答案区间时候加个判断（即[i,j]区间有没有分别出现在两个字符串中）

Accode:

class Solution {
public: 

    string s;
    int n,m;
    int ans =0;
    int cache[2001][2001];
    int dfs(int i,int j){
        if(i>j){
            return 0;
        }
        if(i==j) return 1;
        if(cache[i][j]) return cache[i][j];
        if(s[i]==s[j]){    
            int res = dfs(i+1,j-1)+2;
            if(i<n && j>=n) ans = max(ans,res);
            return cache[i][j] =  res;
        }
        else {
            return cache[i][j] = max(dfs(i+1,j),dfs(i,j-1));
        }
    }
    int longestPalindrome(string word1, string word2) {
        s = word1+word2;
        n = word1.length();
        m = word2.length();
        memset(cache,0,sizeof cache);
        dfs(0,s.length()-1);
        return ans;
    }
};

时间复杂度$o(n^2)$