給一字元串 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