【编程题-错题集】最长回文子序列(动态规划 - 区间dp)

简介: 【编程题-错题集】最长回文子序列(动态规划 - 区间dp)

牛客对应题目链接:最长回文子序列_牛客题霸_牛客网 (nowcoder.com)


一、分析题目

基础的区间 dp 问题:

1、状态表示

dp[i][j] 表示:字符串 [i, j] 区间内的最长回文子序列的长度。


2、状态转移方程

  1. 当 i > j,dp[i][j] = 0(不讨论这种情况,可以保证不存在这种情况)
  2. i == j 的时候,只有⼀个字符,长度为 1,即 dp[i][j] = 1;
  3. i < j 的时候,分情况讨论:
  • s[i] == s[j]dp[i][j] = dp[i+1][j-1] + 2;
  • s[i] != s[j]dp[i][j] = max(dp[i+1][j], dp[i][j-1])

3、初始化

根据状态转移方程,可以知道 dp[i][j] 的取值方向只会从它的左边、左下、下面三个方向去取,而这些方向除了 i==j 时是初始化为 1 的以外,其它的都是 i > j,不需要另外进行初始化。


4、填表顺序

从下往上,从左往右。


5、返回值

dp[0][n-1](可以返回状态表示的含义去思考返回值)


二、代码

1、力扣AC代码

//动态规划-二维dp
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(i==j) dp[i][j]=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];
    }
};
 
//动态规划-二维dp-优化
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        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];
    }
};

2、值得学习的代码

#include <iostream>
#include <string>
 
using namespace std;
 
int dp[1010][1010];
 
int main()
{
    string s;
    cin >> s;
    int n = s.size();
 
    for(int i = n - 1; i >= 0; i--)
    {
        dp[i][i] = 1;
        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]);
        }
    }
 
 cout << dp[0][n - 1] << endl;
 
 return 0;
}

三、反思与改进

做这道题时,我还是想到了之前写过的5. 最长回文子串 - 力扣(LeetCode),然后就还是按着之前的分类讨论的思路去写了,结果只能通过一般的测试样例。忽略了这两道题目的不同之处:之前写的题目要求的是子串,说明是连续序列;而这道题目要求的是子序列,并没有要求是连续的,所以这两道题目的解法肯定不一样。

本题应该是与516. 最长回文子序列 - 力扣(LeetCode)要求一致,不过这道题之前也写过,印象不深刻,说明没有掌握这类题目的本质,不熟练就多做几次吧。


目录
打赏
0
0
0
0
9
分享
相关文章
【已解决】Flask当中render_template函数使用过程当中css文件无法正常渲染
【已解决】Flask当中render_template函数使用过程当中css文件无法正常渲染
论文介绍:机器学习中数据集规模增长的极限分析
【5月更文挑战第17天】论文《机器学习中数据集规模增长的极限分析》探讨了数据集大小对AI模型性能的影响,预测语言数据可能在2026年前耗尽,图像数据在2030-2060年可能面临相同问题。研究显示数据积累速度无法跟上数据集增长,可能在2030-2040年间导致训练瓶颈。然而,算法创新和新数据源的发展可能缓解这一问题。[链接](https://arxiv.org/pdf/2211.04325.pdf)
225 2
一个 git 仓库下拥有多个项目的 git hooks 配置方案
一个 git 仓库下拥有多个项目的 git hooks 配置方案
319 0
linux安装nginx和前端部署vue项目(实际测试react项目也可以)
本文是一篇详细的教程,介绍了如何在Linux系统上安装和配置nginx,以及如何将打包好的前端项目(如Vue或React)上传和部署到服务器上,包括了常见的错误处理方法。
2726 0
linux安装nginx和前端部署vue项目(实际测试react项目也可以)
如何在StableDiffusionWebUI 中使用Civital网站的LoRA模型?
如何在StableDiffusionWebUI 中使用Civital网站的LoRA模型?
660 0
c++动态内存管理(一)
C++ 动态内存管理 在 C++ 中,动态内存管理是一个核心概念,它允许在运行时分配和释放内存。以下是 C++ 动态内存管理需要掌握的关键知识点:
240 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等