PHP を使用して最長増加サブシーケンス アルゴリズムを作成する方法

PHP を使用して最長増加部分列アルゴリズムを作成する方法

はじめに:
最長増加部分列は古典的なコンピューティングの問題です。シーケンス内の最長増加部分列を見つけることです。コンピューター サイエンスでは、この問題に対する解決策は数​​多くありますが、その 1 つが動的プログラミングです。この記事では、PHP を使用して最長増加部分列アルゴリズムを作成する方法とコード例を紹介します。

ステップ 1: 最長増加部分列の問題を理解する
アルゴリズムを書き始める前に、まず最長増加部分列の定義を理解する必要があります。シーケンス A が与えられた場合、B が厳密に増加するような最長のサブシーケンス B を見つけたいとします。たとえば、シーケンス A = [2, 4, 3, 5, 1, 7, 6, 9, 8] の場合、その最も長く増加するサブシーケンスは B = [2, 3, 5, 7, 9] で、長さは5の。

ステップ 2: 動的計画法を使用して問題を解決する
動的計画法は、最長増加部分列問題を解決する効果的な方法です。配列 dp[i] を介して、A[i] で終わる最長の増加サブシーケンスの長さを記録できます。次に、配列 A をループして dp 配列を更新することにより、最も長く増加するサブシーケンスの長さを取得します。

コード例:
以下は、PHP で書かれた最長増加サブシーケンス アルゴリズムのサンプル コードです:

function longestIncreasingSubsequence($arr) {
    $n = count($arr);
    $dp = array_fill(0, $n, 1); // 初始化 dp 数组，每个元素的初始值都为 1

    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$i] > $arr[$j]) {
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
    }

    $maxLength = max($dp); // 最长递增子序列的长度

    return $maxLength;
}

$arr = [2, 4, 3, 5, 1, 7, 6, 9, 8];
$length = longestIncreasingSubsequence($arr);
echo "最长递增子序列的长度为：".$length;

上記のコードを実行すると、最長増加サブシーケンスの長さが 5 として出力されます。 、前の例と一致します。

ステップ 3: 最適化アルゴリズム
上記の動的計画法アルゴリズムを通じて、最も長く増加する部分列の長さを取得できますが、特定の部分列を取得することはできません。最も長く増加するサブシーケンスの特定の要素も取得したい場合は、アルゴリズムをわずかに最適化できます。

コード例:
以下は、最長増加サブシーケンス アルゴリズム用にさらに最適化されたサンプル コードです:

function longestIncreasingSubsequence($arr) {
    $n = count($arr);
    $dp = array_fill(0, $n, 1); // 初始化 dp 数组，每个元素的初始值都为 1

    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$i] > $arr[$j]) {
                if ($dp[$j] + 1 > $dp[$i]) {
                    $dp[$i] = $dp[$j] + 1;
                    $prev[$i] = $j; // 记录递增子序列的上一个元素的下标
                }
            }
        }
    }

    $maxLength = max($dp); // 最长递增子序列的长度

    // 构建最长递增子序列
    $index = array_search($maxLength, $dp);
    $lis = [];
    while ($index !== null) {
        $lis[] = $arr[$index];
        $index = $prev[$index] ?? null;
    }

    $lis = array_reverse($lis); // 反转子序列，得到递增顺序

    return [
        'length' => $maxLength,
        'sequence' => $lis
    ];
}

$arr = [2, 4, 3, 5, 1, 7, 6, 9, 8];
$result = longestIncreasingSubsequence($arr);
echo "最长递增子序列的长度为：".$result['length']."<br>";
echo "最长递增子序列为：".implode(', ', $result['sequence']);

上記のコードを実行すると、最長増加サブシーケンスの長さが 5 として出力されます。そして、最も長く増加する部分列を [2, 3, 5, 7, 9] として出力します。

概要:
この記事では、PHP を使用して最長増加サブシーケンス アルゴリズムを作成する方法を紹介し、コード例を示します。動的計画法の考え方を通じて、最長増加部分列の問題を効率的に解くことができます。この記事が、最長増加部分列アルゴリズムを学習して使用したいと考えている読者に役立つことを願っています。

以上がPHP を使用して最長増加サブシーケンス アルゴリズムを作成する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。