题目描述补充

题目：最长的回文序列

给定一个字符串 s，找到 s 中最长的回文子序列的长度。回文是指一个字符串正读和反读都一样的字符串。子序列是指从原字符串中删除某些（也可以不删除）字符而不改变剩余字符的相对顺序所得到的一个新字符串。

示例 1:

输入: s = "cbbd"
输出: 4
解释: 最长的回文子序列是 "bbbb"，其长度为 4。

示例 2:

输入: s = "cbbdb"
输出: 5
解释: 最长的回文子序列是 "cbdbd"，其长度为 5。

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 代码示例

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 代码示例

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

码小课网站中有更多相关内容分享给大家学习，包括但不限于动态规划、字符串处理等算法问题的详细解析和代码实现。