PHP 最长回文子序列

什么是回文

回文是指一个单词、短语、数字或字符序列，从前往后和从后往前读都一样。换句话说，当其字符被颠倒时，它保持不变。

示例

• “level” 是一个回文，因为它从左到右和从右到左读起来都一样。

• “racecar” 是一个回文。

• “12321” 是一个回文。

• “madam” 是一个回文。

最长回文子序列的PHP程序

设X[0..n-1]为长度为n的输入序列，L(0, n-1)为X[0..n-1]的最长回文子序列的长度。 如果X的第一个字符和最后一个字符相同，则L(0, n-1) = L(1, n-2) + 2。 否则L(0, n-1) = MAX (L(1, n-1), L(0, n-2))。

动态规划解决方案

<?php
// A Dynamic Programming based
// PHP program for LPS problem
// Returns the length of the
// longest palindromic
// subsequence in seq

// A utility function to get
// max of two integers
// function max( x,y)
// { return (x>y)? x :y; }

// Returns the length of the
// longest palindromic
// subsequence in seq
function lps(str)
{n = strlen(str);i; j;cl;

// Create a table to store
// results of subproblems
L[][] = array(array());

// Strings of length 1 are
// palindrome of length 1
for (i = 0; i<n; i++)L[i][i] = 1;

    // Build the table. Note that
    // the lower diagonal values
    // of table are useless and
    // not filled in the process.
    // The values are filled in a
    // manner similar to Matrix
    // Chain Multiplication DP
    // cl is length of substring
    for (cl = 2;cl <= n;cl++)
    {
        for (i = 0;i < n -cl + 1; i++)
        {j = i +cl - 1;
            if (str[i] == str[j] &&
                            cl == 2)L[i][j] = 2;
            else if (str[i] == str[j])
            L[i][j] =L[i + 1][j - 1] + 2;
            else
            L[i][j] = max(L[i][j - 1],
                            L[i + 1][j]);
        }
    }

    returnL[0][n - 1];
}

// Driver Codeseq = 'BBABCBCAB';
n = strlen(seq);
echo "The length of the " .
    " longest palindromic subsequence is ", lps($seq);
?>

输出

The length of the longest palindromic subsequence is 7

给定代码在使用输入字符串“BBABCBCAB”执行时的输出是最长回文子序列的长度为7.这意味着在输入字符串“BBABCBCAB”中存在长度为7的回文子序列，即 BABCBAB.“BBBBB”和“BBCBB”也是给定序列的回文子序列，但不是最长的。该代码成功使用动态规划计算并返回这个长度。

结论

总之，提供的PHP代码实现了在给定字符串中找到最长回文子序列长度的动态规划解决方案。当使用输入字符串“BBABCBCAB”执行时，它正确地确定最长回文子序列的长度是7（BABCBAB）。然而，代码并没有明确提供子序列本身。它通过构建不同子字符串的长度表来工作，考虑到字符匹配与否的情况。该算法使用自底向上的方法高效地计算出长度，得到所需的输出。