数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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]);
}
}
return $L[0][$n - 1];
}
// Driver Code
$seq = '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）。但是，该代码没有明确提供子序列本身。它通过构建不同子字符串的长度表来工作，考虑字符匹配或不匹配的情况。该算法使用自底向上的方法有效地计算长度，从而得到所需的输出。
更新于： 2023年8月1日
301 次浏览
广告