一开始以为是最长回文子串,这题就跟上题基本一致了,代码如下。但是题目所说的是最长回文子序列,此时就相当于做了两题了。
最长回文子串代码:
class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),false));int result = 1; for(int i = s.size()-1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(s[i] == s[j]) {if(j - i <= 1){dp[i][j] = true;}else if(dp[i+1][j-1]){dp[i][j] = true;if(j - i+1 > result) result = j-i+1;}}}}return result;}
};
最长回文子序列:
力扣:516.最长回文子序列
题目:
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
解析:
然后还是很简单的,几分钟的事,还是首先通过for循环确定为二维dp数组,然后其含义为题目目的即 i ~ j 的最长回文子序列长度。然后脑海中举一个例子,然后考虑所有情况,用dp数组将其表示出来。
递归公式:
- 如果s[i]与s[j]相同,那么dp[i][j] = dp[i + 1][j - 1] + 2;
- 如果s[i]与s[j]不相同最长回文序列有两种情况,包含 i 的,包含 j 的,所以只需要进行比较即可。
初始化:
因为在递归公式中。当s【i】 == s【j】这种情况中其dp就默认了 i j 之间的长度大于1。所以应该考虑为 j - i 为1的情况。主观来看很明显应该是1。然后按照含义,递归公式,模拟遍历来初始化。此时按照含义即可初始化完成。其他情况dp[i][j]初始为0就行,这样递推公式:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。
递归顺序:
与上题分析一致。
最长回文子序列代码:
class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));for(int i = 0; i < s.size(); ++i) dp[i][i] = 1;for(int i = s.size()-1; i >= 0; --i){for(int j = i+1; j < s.size(); ++j){if(s[i] == s[j]){dp[i][j] = 2+dp[i+1][j-1]; }else {dp[i][j] = max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][s.size()-1];}
};