題目地址(516. 最長回文子序列)
https://leetcode-cn.com/problems/longest-palindromic-subsequence/
題目描述
給定一個字符串 s 斜友，找到其中最長的回文子序列橄霉，并返回該序列的長度。可以假設 s 的最大長度為 1000 。
示例 1:
輸入:
"bbbab"
輸出:
4
一個可能的最長回文子序列為 "bbbb"。
示例 2:
輸入:
"cbbd"
輸出:
2
一個可能的最長回文子序列為 "bb"。
提示：
1 <= s.length <= 1000
s 只包含小寫英文字母
思路
假設dp[i][j]為i到j的最長子序列贤惯，當i=j時，單個字符棒掠，最長回文子序列就是他自己孵构，為1.
先往兩邊擴展，可以就直接拓展2個烟很，不行就看往左拓展回文子序列長還是往右拓展一個字符子序列長颈墅。
如果s[i]==s[j]，說明當前兩個字符可以納入回文子序列雾袱，此時dp[i][j]=dp[i+1][j-1]+2, (前一個狀態(tài)dp[i+1][j-1]直接拓展兩個長度)這是從最右邊逐個字符往兩邊拓展恤筛。
如果s[i]!=s[j]，dp[i][j] = Max(dp[i+1][j], dp[i][j-1])芹橡，s[i]和sj對構成回文子序列沒用毒坛，i到j的最長回文子序列就為，前一個狀態(tài)s[i+1][j-1]向右拓展一個字符或向左拓展一個字符的回文子序列的最大值。
題解
/**
* @Author: vividzcs
* @Date: 2021/2/2 11:22 下午
*/
public class LongestSubSquence {
public static void main(String[] args) {
String s = "bbbab";
int len = getLongestSubSquence(s);
System.out.println(len);
}
private static int getLongestSubSquence(String s) {
if (s == null || s.length() <= 2) {
return s.length();
}
int[][] dp = new int[s.length()][s.length()];
for (int i=0; i<dp.length; i++) {
dp[i][i] = 1;
}
for (int i=s.length() - 1; i >= 0; i--) {
for (int j=i+1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][s.length()-1];
}
}
