回文とは何ですか?

回文とは、後ろから読んでも前から読んでも同じように読める単語、語句、数字、または一連の文字です。つまり、文字を反転しても変化しません。

例

• "level" は、左から右、右から左に読んでも同じなので回文です。

• 「レースカー」は回文です。

• 「12321」は回文です。

• 「マダム」は回文です。

最長回文部分列用の 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)).

動的プログラミング ソリューション

 $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 

出力

The length of the longest palindromic subsequence is 7

入力文字列 "BBABCBCAB" を使用して実行した場合の指定されたコードの出力は、最長回文サブシーケンスの長さは 7 です。これは、入力文字列 "BBABCBCAB" 内に長さ 7 の回文サブシーケンスが存在することを意味します。つまりバブバブ。 BBBBB」と「BBCBB」も、指定されたシーケンスの回文サブシーケンスですが、最長のものではありません。コードは動的プログラミングを使用してこの長さを正常に計算し、返します。

結論

結論として、提供された PHP コードは、指定された文字列内の最長の回文サブシーケンスの長さを見つける動的プログラミング ソリューションを実装しています。入力文字列「BBABCBCAB」を指定して実行すると、最長の回文サブシーケンスの長さが 7(BABCBAB) であると正しく判断されます。ただし、コードはサブシーケンス自体を明示的に提供しません。これは、文字が一致する場合と一致しない場合を考慮して、さまざまな部分文字列の長さのテーブルを作成することで機能します。このアルゴリズムはボトムアップのアプローチを使用して長さを効率的に計算し、目的の出力をもたらします。