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

发布于:2025-03-16 ⋅ 阅读:(14) ⋅ 点赞:(0)

思路来源 灵茶山艾府

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

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

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];
    }
};


网站公告

今日签到

点亮在社区的每一天
去签到