PHP アルゴリズム分析: 動的プログラミング アルゴリズムを使用して最長回文部分文字列問題を解決するにはどうすればよいですか?

PHP アルゴリズム分析: 動的計画アルゴリズムを使用して最長回文部分文字列問題を解決するにはどうすればよいですか?

動的計画法 (ダイナミック プログラミング) は、多くの複雑な問題を解決できる、一般的に使用されるアルゴリズムのアイデアです。そのうちの 1 つは、最長回文部分文字列の問題です。これは、文字列内の最長回文部分文字列の長さを見つけることです。この記事では、PHP を使用してこの問題を解決する動的プログラミング アルゴリズムを作成する方法を紹介し、具体的なコード例を示します。

最初に最長の回文部分文字列を定義します。回文文字列は前方と後方で同じように読める文字列を指しますが、回文部分文字列は元の文字列内の連続した回文文字列です。たとえば、文字列「level」では、「eve」は回文部分文字列です。

最長回文部分文字列問題を解決するには、動的計画法アルゴリズムのアイデアを使用できます。具体的には、2 次元配列 dp を使用して、文字列内の各部分文字列が回文文字列であるかどうかを表すことができます。 dpi は、i 番目の文字から j 番目の文字までで構成される部分文字列が回文文字列であるかどうかを示します。 dpi が true の場合、i 番目の文字から j 番目の文字までの部分文字列は回文部分文字列になります。

次に、状態遷移方程式、つまり、既知の dpi に基づいて dpi 1 の値を推定する方法を見つける必要があります。回文文字列の特性によれば、dpi が true の場合、dpi 1 の値は、i 番目の文字と j 番目の文字が等しいかどうかに依存することがわかります。それらが等しい場合は、i 番目の文字から j 番目の文字までの部分文字列が回文文字列であるかどうか、つまり dpi 1 の値であるかどうかを判断するだけで済みます。それ以外の場合、dpi 1 は false になります。

状態遷移方程式を使用すると、最長回文部分文字列問題を解決するための PHP コードを書き始めることができます。

function longestPalindrome($s) {
    $n = strlen($s);
    $dp = array_fill(0, $n, array_fill(0, $n, false)); // 初始化dp数组，默认都为false

    // 初始化最长回文子串的起始位置和长度
    $start = 0;
    $maxLen = 1;

    // 单个字符都是回文子串
    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = true;
    }

    // 根据状态转移方程计算dp数组
    for ($j = 1; $j < $n; $j++) {
        for ($i = 0; $i < $j; $i++) {
            if ($s[$i] == $s[$j]) {
                if ($j - $i <= 2 || $dp[$i + 1][$j - 1]) {
                    $dp[$i][$j] = true;
                    if ($j - $i + 1 > $maxLen) {
                        $maxLen = $j - $i + 1;
                        $start = $i;
                    }
                }
            }
        }
    }

    return substr($s, $start, $maxLen); // 返回最长回文子串
}

// 测试示例
$str = "babad";
echo longestPalindrome($str);

上記のコードでは、最長回文部分文字列問題を解決する関数 longestPalindrome を定義しています。この関数は文字列 $s をパラメータとして受け取り、最長の回文部分文字列を返します。この関数では、まず dp 配列を初期化し、個々の文字を回文部分文字列としてマークします。次に、状態遷移方程式に従って dp 配列を計算します。最後に、開始位置と長さに基づいて最長の回文部分文字列を返します。

サンプル コードでは、テスト文字列は「babad」で、出力結果は「bab」です。これは最長の回文部分文字列です。

動的計画法アルゴリズムを使用すると、最長回文部分文字列問題を効率的に解くことができます。この記事が動的プログラミング アルゴリズムの理解と応用に役立つことを願っています。

以上がPHP アルゴリズム分析: 動的プログラミング アルゴリズムを使用して最長回文部分文字列問題を解決するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。