Analyse de l'algorithme PHP : Comment utiliser un algorithme de programmation dynamique pour résoudre le problème de sous-séquence courante le plus long ?

Analyse d'algorithme PHP : Comment utiliser un algorithme de programmation dynamique pour résoudre le problème de sous-séquence commune le plus long ?

La programmation dynamique est une méthode d'optimisation mathématique généralement utilisée pour résoudre des problèmes avec des sous-problèmes qui se chevauchent et des propriétés de sous-structure optimales. Parmi eux, le problème de sous-séquence le plus courant est un problème de programmation dynamique classique, qui a de nombreuses applications dans des domaines tels que le traitement des chaînes, la théorie des graphes et la bioinformatique.

Le problème de la sous-séquence commune la plus longue peut être brièvement décrit comme : étant donné deux chaînes s1 et s2, trouvez leur sous-séquence commune la plus longue (LCS). Une sous-séquence d'une chaîne est une chaîne obtenue en supprimant certains caractères de la chaîne d'origine sans modifier l'ordre des autres caractères.

Par exemple, pour les chaînes s1 = "ABCD" et s2 = "ACDF", leur sous-séquence commune la plus longue est "ACD".

Ensuite, utilisons le langage PHP pour implémenter l'algorithme de programmation dynamique afin de résoudre le problème de sous-séquence commune le plus long.

function longestCommonSubsequence($s1, $s2) {
    $m = strlen($s1);
    $n = strlen($s2);
    $dp = array();

    // 初始化边界条件
    for ($i = 0; $i <= $m; $i++) {
        $dp[$i][0] = 0;
    }
    for ($j = 0; $j <= $n; $j++) {
        $dp[0][$j] = 0;
    }

    // 动态规划计算最长公共子序列长度
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($s1[$i - 1] == $s2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    // 构造最长公共子序列字符串
    $lcs = "";
    $i = $m;
    $j = $n;
    while ($i > 0 && $j > 0) {
        if ($s1[$i - 1] == $s2[$j - 1]) {
            $lcs = $s1[$i - 1] . $lcs;
            $i--;
            $j--;
        } else {
            if ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
                $i--;
            } else {
                $j--;
            }
        }
    }

    return $lcs;
}

// 测试
$s1 = "ABCD";
$s2 = "ACDF";
echo "最长公共子序列：" . longestCommonSubsequence($s1, $s2);

Dans le code ci-dessus, nous avons défini la fonction longestCommonSubsequence, qui accepte deux chaînes s1 et s2 et renvoie leur sous-séquence publique la plus longue. longestCommonSubsequence函数，它接受两个字符串s1和s2，并返回它们的最长公共子序列。

我们使用了一个二维数组$dp来记录计算过程中的中间结果。首先，我们初始化边界条件，即当一个字符串为空时，最长公共子序列的长度为0。

然后，我们使用两个嵌套的循环来计算最长公共子序列的长度。如果当前字符相等，则选择两个字符串都去掉最后一个字符后的最长公共子序列的长度加1；如果当前字符不相等，则选择两个字符串中去掉一个字符后的最长公共子序列的长度的较大值。

最后，我们利用中间结果的二维数组$dp

Nous utilisons un tableau bidimensionnel $dp pour enregistrer les résultats intermédiaires pendant le processus de calcul. Tout d’abord, nous initialisons la condition aux limites, c’est-à-dire que lorsqu’une chaîne est vide, la longueur de la sous-séquence commune la plus longue est 0.

Ensuite, nous utilisons deux boucles imbriquées pour calculer la longueur de la sous-séquence commune la plus longue. Si les caractères actuels sont égaux, sélectionnez la longueur de la sous-séquence commune la plus longue des deux chaînes après avoir supprimé le dernier caractère plus 1 ; si les caractères actuels ne sont pas égaux, sélectionnez la sous-séquence commune la plus longue des deux chaînes après avoir supprimé un caractère. valeur plus grande de la longueur de la séquence.

Enfin, nous utilisons le tableau bidimensionnel $dp du résultat intermédiaire pour construire la chaîne de la sous-séquence commune la plus longue. Plus précisément, nous partons du coin inférieur droit, si les caractères actuels sont égaux, nous les ajoutons à la chaîne de sous-séquence commune la plus longue, puis déplaçons le pointeur vers le coin supérieur gauche. Si les caractères actuels ne sont pas égaux, la direction de déplacement du pointeur est déterminée sur la base des résultats des calculs de programmation dynamique. 🎜🎜Enfin, nous testons les exemples de chaînes "ABCD" et "ACDF" et générons la sous-séquence commune la plus longue "ACD". 🎜🎜Grâce au code ci-dessus, nous avons utilisé un algorithme de programmation dynamique pour résoudre le problème de sous-séquence commune le plus long et vérifié l'exactitude et la faisabilité de l'algorithme à l'aide d'exemples. Dans des applications pratiques, nous pouvons utiliser cet algorithme pour résoudre divers problèmes de traitement de chaînes et améliorer l'efficacité et la précision du programme. 🎜

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!