题目描述：
给定一个字符串 s，找到其中的最长回文子序列并返回其长度。回文子序列是指不改变剩余字符顺序的情况下，从字符串中删除某些字符或不删除任何字符而形成的子序列。
示例：
输入：s = “bbbab”
输出：4，可能的回文子序列为 “bbbb”。
输入：s = “cbbd”
输出：2，可能的回文子序列为 “bb”。
解决方案：
这里我们使用动态规划的方法来解决这个问题。对于一个子序列而言，如果它是回文子序列并且长度大于2，那么去除首尾两个字符后，它仍然是一个回文子序列。我们可以通过动态规划计算给定字符串的最长回文子序列。
我们定义一个二维数组 dp，其中 dp[i][j] 表示字符串 s 的下标范围 [i, j] 内的最长回文子序列的长度。当 0≤i≤j0，否则 dp[i][j]=0。任何长度为 1 的子序列都是回文子序列，所以动态规划的边界情况是 dp[i][i]=1。
当 i
1. 如果 s[i] 和 s[j] 相等，那么我们可以在 s 的下标范围 [i+1][j-1] 的最长回文子序列的基础上，通过在首尾分别添加 s[i] 和 s[j]，得到 s 的下标范围 [i][j] 的最长回文子序列。dp[i][j]=dp[i+1][j-1]+2。
2. 如果 s[i] 和 s[j] 不相等，那么 s[i] 和 s[j] 不能同时作为同一个回文子序列的开头和结尾。dp[i][j]=max(dp[i+1][j], dp[i][j-1])。
最终，dp[0][n-1] 就是字符串 s 的最长回文子序列的长度。
不同编程语言的实现：
Java:
java
public class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n – 1; i >= 0; i–) {
dp[i][i] = 1;
for (int j = i + 1; 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][n – 1];
}
C:
csharp
public class Solution {
public int LongestPalindromeSubseq(string s) {
int n = s.Length;
int[,] dp = new int[n, n];
for (int i = n – 1; i >= 0; i–) {
dp[i, i] = 1;
for (int j = i + 1; j
if (s[i] == s[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, n – 1];
}
JavaScript:
javascript
function longestPalindromeSubseq(s) {
const n = s.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = n – 1; i >= 0; i–) {
dp[i][i] = 1;
for (let j = i + 1; j
if (s[i] === s[j]) {
dp[i][j] = dp[i +
