题目地址(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, (前一个状态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的最长回文子序列就为，前一个状态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];
}
}
