Comment écrire l'algorithme de sous-séquence croissante la plus longue en utilisant PHP

Comment écrire l'algorithme de sous-séquence croissante la plus longue en utilisant PHP

Introduction :
La sous-séquence croissante la plus longue est un problème informatique classique, qui consiste à trouver la sous-séquence croissante la plus longue dans une séquence. En informatique, il existe de nombreuses solutions à ce problème, dont la programmation dynamique. Cet article explique comment écrire l'algorithme de sous-séquence croissante la plus longue à l'aide de PHP et fournit des exemples de code.

Étape 1 : Comprendre le problème de la sous-séquence croissante la plus longue
Avant de commencer à écrire l'algorithme, vous devez d'abord comprendre la définition de la sous-séquence croissante la plus longue. Étant donné une suite A, on veut trouver la sous-suite B la plus longue telle que B soit strictement croissante. Par exemple, pour la séquence A = [2, 4, 3, 5, 1, 7, 6, 9, 8], sa sous-séquence croissante la plus longue est B = [2, 3, 5, 7, 9], avec une longueur de 5.

Étape 2 : Utiliser la programmation dynamique pour résoudre le problème
La programmation dynamique est une méthode efficace pour résoudre le problème de sous-séquence croissante la plus longue. Nous pouvons enregistrer la longueur de la sous-séquence croissante la plus longue se terminant par A[i] via un tableau dp[i]. Ensuite, nous obtenons la longueur de la sous-séquence croissante la plus longue en parcourant le tableau A et en mettant à jour le tableau dp.

Exemple de code :
Voici un exemple de code pour l'algorithme de sous-séquence croissante la plus longue écrit en 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;

L'exécution du code ci-dessus affichera la longueur de la sous-séquence croissante la plus longue de 5, conformément à notre exemple précédent.

Étape 3 : Algorithme d'optimisation
Grâce à l'algorithme de programmation dynamique ci-dessus, nous pouvons obtenir la longueur de la sous-séquence croissante la plus longue, mais nous ne pouvons pas obtenir la sous-séquence spécifique. Si l’on souhaite également obtenir les éléments spécifiques de la sous-séquence croissante la plus longue, on peut légèrement optimiser l’algorithme.

Exemple de code :
Ce qui suit est un exemple de code optimisé pour l'algorithme de sous-séquence croissante la plus longue :

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']);

L'exécution du code ci-dessus affichera la longueur de la sous-séquence croissante la plus longue comme 5 et imprimera la sous-séquence croissante la plus longue comme [2 , 3, 5, 7, 9].

Résumé :
Cet article explique comment écrire l'algorithme de sous-séquence croissante la plus longue à l'aide de PHP et fournit des exemples de code. Grâce à l'idée de programmation dynamique, nous pouvons résoudre efficacement le problème de la sous-séquence croissante la plus longue. J'espère que cet article sera utile aux lecteurs qui souhaitent apprendre et utiliser l'algorithme de sous-séquence croissante la plus longue.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!