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']."
"; 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!