wordpress做的网站扩展性,wordpress竖直导航栏,如何下载网页上的视频,深圳上市公司一览表给你一个字符串 s #xff0c;找出其中最长的回文子序列#xff0c;并返回该序列的长度。
子序列定义为#xff1a;不改变剩余字符顺序的情况下#xff0c;删除某些字符或者不删除任何字符形成的一个序列。 示例 1#xff1a;
输入#xff1a;s bbbab
输出…给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。 示例 1
输入s bbbab
输出4
解释一个可能的最长回文子序列为 bbbb 。示例 2
输入s cbbd
输出2
解释一个可能的最长回文子序列为 bb 。提示
1 s.length 1000s 仅由小写英文字母组成
class Solution {
public:int longestPalindromeSubseq(string s) {//如果 s[i] s[j],且[i1 - j-1]区间是回文字串那么目前的总长度就是在原来的基础上2 想要求 [1,4]就得先知道[2,3]的情况。所以i方向//dp定义dp[i][j]:[i-j]区间的最长回文子序列为 dp[i][j];vectorvectorintdp(s.size()1,vectorint(s.size()1,0));//递推关系1、如果 s[i] s[j]; 且那么 目前的最长长度为 dp[i1][j-1]2//2、如果s[i] ! s[j].那么最起码有 dp[i1][j-1]这么长(继承)。再加上分别考虑s[i]加入的情况 和 s[j]加入的情况。即dp[i1][j] dp[i][j-1];//初始化如果 ij那么单个字符 也算一个回文串for(int i 0;i s.size();i){dp[i][i] 1;}//遍历顺序想要求 [1,4]就得先知道[2,3]的情况。所以i方向从后往前。j方向从前往后。for(int i s.size()-1;i 0;i--){for(int j i1;j s.size();j){if(s[i] s[j]) dp[i][j] dp[i1][j-1] 2;else dp[i][j] max(dp[i1][j], dp[i][j-1]);// 下方 左方}}return dp[0][s.size()-1];}
};
