(动态规划 区间dp/dfs 最长回文子序列）leetcode 516

思路来源 灵茶山艾府

题目要求找到最长 回文 子序列

选或者不选 从两侧向内缩小问题规模、

if(s[i]==s[j])

return dfs(i+1,j-1)+2//从0--s.size()的最长公共子序列的长度为，1--s.size()-1的最长公共子序列的长度+2 

else

if(s[i]!=s[j])

return max(dfs(i+1,j),dfs(i,j-1));

不相同，左右两边的字符分别消掉对方再比较最大值

边界条件

if i>j

return 0

if(i==j)

return 1;

利用记忆化搜索

代码如下

class Solution {
    vector<vector<int>>used;
int dfs(string &s,int i,int j)
{
    
    if (i == j)
        return 1;
    if (i > j)
        return 0;
    if(used[i][j]!=-1)
    return used[i][j];
    if (s[i] != s[j])
    {
        used[i][j]=max(dfs(s, i + 1, j), dfs(s, i, j - 1));

    }
    else
    {
        used[i][j]=dfs(s, i + 1, j -1)+2;
    }

return used[i][j];
}
public:

    int longestPalindromeSubseq(string s) {
       used=vector<vector<int>>(s.size()+1,vector<int>(s.size()+1,-1));
        return dfs(s,0,s.size()-1);
    }
};

然后是改成递推

这里用的是二维数组，每个数组的含义是

从下标i到j的范围，最长的回文子序列

ai解释：

• i 是子串的起点，j 是子串的终点。
• dp[i][j] 的值依赖于更小的子问题，如 dp[i+1][j] 或 dp[i][j-1]。
• dp[i][j] 的值依赖于更小的子问题，如 dp[i+1][j] 或 dp[i][j-1]。

• 例子 假设 s = "abdbca"，我们看 dp[1][4]，也就是子串 "bdb"：

• s[1] = 'b'，s[4] = 'b'，满足 s[i] == s[j]。
• 去掉 s[1] 和 s[4] 后，s[2:3] = "d"，这个子串的最长回文子序列是 1。
• 所以 dp[1][4] = dp[2][3] + 2 = 1 + 2 = 3（即 "bdb"）。

代码如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
vector<vector<int>>dp(n+ 1, vector<int>(n + 1, 0));  
for (int i = 0;i < n;i++)
{
    dp[i][i] = 1;
}

for(int i = n - 1;i >= 0;i--)
{
    for (int j = i + 1;j < n;j++)
    {
        if (s[i] == s[j])
        {
            dp[i][j]=dp[i + 1][j - 1] + 2;
        }
        else
        {
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

        }
    }
}
return dp[0][n-1];
    }
};