给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.
在线评测地址:领扣题库官网
样例1
输入: "bbbab"
输出: 4
解释:
一个可能的最长回文序列为 "bbbb"
样例2
输入: "bbbbb"
输出: 5
算法:DP
设dpi表示在s[i...j]中最长回文序列的长度。
对于初始化区间长度
- 长度为0时,dpi = 1
-
对于 dpi,假设s[i] != s[j]
- 那么在sub(i,j)的最大回文串中,s[i]与s[j]不会同时出现,那么sub(i,j)的最大回文串要么出现在sub(i+1,j),要么出现在sub(i,j-1),因此我们的状态转移方程就得到了dpi = max(dpi+1, dpi)
-
假设s[i]==s[j]
- 那么直接认为这俩个匹配,会同时出现在结果中,然后加上sub(i+1,j-1)的最大回文串,即dpi = dpi+1 + 2
- 最后的结果就在dp0
复杂度分析
-
时间复杂度O(len(s)*len(s))
- 嵌套循环,顺着i减小的方向,以j增大的方向遍历
-
空间复杂度O(len(s)*len(s))
- 二维dp的大小
public class Solution {
/**
* @param s: the maximum length of s is 1000
* @return: the longest palindromic subsequence's length
*/
public int longestPalindromeSubseq(String s) {
int size = s.length();
char[] ss = s.toCharArray();
if (size <= 1){
return size;
}
int[][] dp = new int[size][size];
//初始化
for (int i = 0; i < size; ++i) {
dp[i][i] = 1;
}
for (int i = size - 1; i >= 0; --i) {
for (int j = i + 1; j < size; ++j) {
if (ss[i] == ss[j]) {//s[i]==s[j]时的转移方程
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else {//s[i]!=s[j]时的转移方程
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
//最后结果在dp[0][size - 1]中
return dp[0][size - 1];
}
}
更多题解参考:九章官网solution