当前位置： 面试刷题>> 最长的回文序列 (经典算法题500道)
### 题目描述补充
题目：**最长的回文序列**
给定一个字符串 `s`，找到 `s` 中最长的回文子序列的长度。回文是指一个字符串正读和反读都一样的字符串。子序列是指从原字符串中删除某些（也可以不删除）字符而不改变剩余字符的相对顺序所得到的一个新字符串。
**示例 1**:
```
输入: s = "cbbd"
输出: 4
解释: 最长的回文子序列是 "bbbb"，其长度为 4。
```
**示例 2**:
```
输入: s = "cbbdb"
输出: 5
解释: 最长的回文子序列是 "cbdbd"，其长度为 5。
```
### PHP 代码示例
```php
function longestPalindromeSubseq($s) {
$n = strlen($s);
$dp = array_fill(0, $n, array_fill(0, $n, 0));
for ($i = $n - 1; $i >= 0; $i--) {
$dp[$i][$i] = 1;
for ($j = $i + 1; $j < $n; $j++) {
if ($s[$i] == $s[$j]) {
$dp[$i][$j] = $dp[$i + 1][$j - 1] + 2;
} else {
$dp[$i][$j] = max($dp[$i + 1][$j], $dp[$i][$j - 1]);
}
}
}
return $dp[0][$n - 1];
}
// 示例
echo longestPalindromeSubseq("cbbd"); // 输出 4
echo longestPalindromeSubseq("cbbdb"); // 输出 5
```
### Python 代码示例
```python
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n-1, -1, -1):
dp[i][i] = 1
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
# 示例
print(longestPalindromeSubseq("cbbd")) # 输出 4
print(longestPalindromeSubseq("cbbdb")) # 输出 5
```
### JavaScript 代码示例
```javascript
function longestPalindromeSubseq(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; 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];
}
// 示例
console.log(longestPalindromeSubseq("cbbd")); // 输出 4
console.log(longestPalindromeSubseq("cbbdb")); // 输出 5
```
**码小课**网站中有更多相关内容分享给大家学习，包括但不限于动态规划、字符串处理等算法问题的详细解析和代码实现。