leetcode:516 最长回文字序列

devtools/2024/12/22 3:00:38/

516. 最长回文字序列

题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/

题目描述

给定一个字符串 s,找到 s 中最长的回文子序列。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "bbbab"               
输出: 4
解释: 一个可能的最长回文子序列是 "bbbb"。

示例 2:

输入: "cbbd"        
输出: 2
解释: 一个可能的最长回文子序列是 "bb"。

题目解析

s 中最长的回文子序列长度和s的子序列有关。

因此我们可以采用动态规划解决这个问题。

我们用dp[i][j]表示从i到j的最长回文子序列的长度。

初始化dp[i][i] = 1,表示一个字符就是回文子序列。

然后我们从i到j遍历,填充dp[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])

我们返回dp[0][n-1],其中n是字符串s的长度,即为最长回文子序列的长度。

值得注意的是,我们在遍历填充dp时,由于dp[i][j]的值的计算依赖于dp[i+1][j-1]和dp[i][j-1]以及dp[i-1][j-1],因此我们需要按列,从下往上向前填充dp。

代码实现

class Solution(object):def longestPalindromeSubseq(self, s):n=len(s)dp=[[0]*n for _ in range(n)]for i in range(0,n):dp[i][i]=1for j in range (1,n):for i in range (j-1,-1,-1):if s[i]==s[j]:dp[i][j]=dp[i+1][j-1]+2else :dp[i][j]=max(dp[i+1][j],dp[i][j-1])return dp[0][n-1]
func longestPalindromeSubseq(s string) int {n:=len(s)dp:=make([][]int,n)for i:=range dp{dp[i]=make([]int,n)}for i:=0;i<n;i++{dp[i][i]=1}for j:=1;j<n;j++{for i:=j-1;i>=0;i--{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]
}
class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();auto dp=vector<vector<int>> (n,vector<int>(n));for(int i=0;i<n;i++){dp[i][i]=1;}for(int j=1;j<n;j++){for(int i=j-1;i>=0;i--){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];}
};

http://www.ppmy.cn/devtools/107736.html

相关文章

单元测试、系统测试和集成测试知识详解

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、单元测试的概念 单元测试是对软件基本组成单元进行的测试&#xff0c;如函数或一个类的方法。当然这里的基本单元不仅仅指的是一个函数或者方法&#xff…

MySQL基础:索引

&#x1f48e;所属专栏&#xff1a;MySQL 1. 索引概述 MySQL中的索引是帮助MySQL高效获取数据的数据结构&#xff0c;可以极大地提高数据库的查询效率&#xff0c;减少数据库的I/O成本&#xff0c;就像书的目录一样&#xff0c;它可以帮助我们快速定位到书中的内容。 优势&…

组件化是如何进行通信的

目录 1.接口&#xff08;Interface&#xff09;2.事件总线&#xff08;[Event Bus](https://blog.csdn.net/Sh_12345/article/details/131623985)&#xff09;3. 服务&#xff08;Service&#xff09;4.消息队列&#xff08;Message Queue&#xff09;5.依赖注入&#xff08;De…

9. GIS技术支持工程师岗位职责、技术要求和常见面试题

本系列文章目录&#xff1a; 1. GIS开发工程师岗位职责、技术要求和常见面试题 2. GIS数据工程师岗位职责、技术要求和常见面试题 3. GIS后端工程师岗位职责、技术要求和常见面试题 4. GIS前端工程师岗位职责、技术要求和常见面试题 5. GIS工程师岗位职责、技术要求和常见面试…

leetcode209. Minimum Size Subarray Sum

题目 Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead. Example 1: Input: target 7, nums [2,3,1,…

209.长度最小的子数组

题目 链接&#xff1a;leetcode链接 思路分析&#xff08;滑动窗口&#xff09; 1、为什么会想到使用滑动窗口呢&#xff1f; 首先&#xff0c;子数组是连续的&#xff0c;第二&#xff0c;所有的元素都是正整数&#xff0c;所以子数组的和具有单调性。 所以&#xff0c;对…

进程

进程 进程进程的含义PCB块内存空间进程分类&#xff1a;进程的作用进程的状态进程已经准备好执行&#xff0c;所有的资源都已分配&#xff0c;只等待CPU时间进程的调度 进程相关命6.查询进程相关命令1.ps aux2.top3.kill和killall发送一个信号 函数1.fork();2.getpid3.getppid示…

一台手机一个ip地址吗?手机ip地址泄露了怎么办

在数字化时代&#xff0c;‌手机作为我们日常生活中不可或缺的一部分&#xff0c;‌其网络安全性也日益受到关注。‌其中一个常见的疑问便是&#xff1a;‌“一台手机是否对应一个固定的IP地址&#xff1f;‌”实际上&#xff0c;‌情况并非如此简单。‌本文首先解答这一问题&a…