資料結構
網路
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 次瀏覽
廣告