Analisis algoritma PHP: Bagaimana untuk menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah urutan biasa yang paling lama?

Analisis algoritma PHP: Bagaimana untuk menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah urutan biasa yang paling lama?

#🎜🎜 #Algoritma Pengaturcaraan Dinamik (Pengaturcaraan Dinamik) ialah kaedah pengoptimuman matematik yang biasanya digunakan untuk menyelesaikan masalah dengan sub-masalah yang bertindih dan sifat sub-struktur yang optimum. Antaranya, masalah urutan lazim yang paling lama ialah masalah pengaturcaraan dinamik klasik, yang mempunyai aplikasi luas dalam bidang seperti pemprosesan rentetan, teori graf, dan bioinformatik.

Masalah urutan lazim terpanjang boleh dihuraikan secara ringkas sebagai: diberi dua rentetan s1 dan s2, cari urutan sepunya terpanjang (LCS). Susunan rentetan ialah rentetan yang diperoleh dengan memadam beberapa aksara daripada rentetan asal tanpa mengubah susunan aksara lain.

Sebagai contoh, untuk rentetan s1 = "ABCD" dan s2 = "ACDF", urutan sepunya terpanjangnya ialah "ACD".

Seterusnya, mari kita gunakan bahasa PHP untuk melaksanakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah urutan biasa yang paling lama.

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

Dalam kod di atas, kami mentakrifkan fungsi longestCommonSubsequence, yang menerima dua rentetan s1 dan s2, dan mengembalikan urutan biasa terpanjang mereka.

longestCommonSubsequence函数，它接受两个字符串s1和s2，并返回它们的最长公共子序列。

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

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

最后，我们利用中间结果的二维数组$dpKami menggunakan tatasusunan dua dimensi $dp untuk merekodkan hasil perantaraan semasa proses pengiraan. Pertama, kita memulakan keadaan sempadan, iaitu, apabila rentetan kosong, panjang urutan sepunya terpanjang ialah 0.

Kemudian, kami menggunakan dua gelung bersarang untuk mengira panjang urutan sepunya terpanjang. Jika aksara semasa adalah sama, pilih panjang urutan sepunya terpanjang bagi dua rentetan selepas mengalih keluar aksara terakhir tambah 1 jika aksara semasa tidak sama, pilih urutan sepunya terpanjang daripada dua rentetan itu nilai panjang jujukan yang lebih besar.

Akhir sekali, kami menggunakan tatasusunan dua dimensi hasil perantaraan $dp untuk membina rentetan urutan sepunya terpanjang. Khususnya, kita bermula dari sudut kanan bawah, jika aksara semasa adalah sama, tambahkannya pada rentetan urutan sepunya terpanjang, dan kemudian alihkan penunjuk ke kiri atas. Jika aksara semasa tidak sama, arah bergerak penunjuk ditentukan berdasarkan hasil pengiraan pengaturcaraan dinamik.

#🎜🎜#Akhir sekali, kami menguji rentetan contoh "ABCD" dan "ACDF" dan mengeluarkan jujukan biasa terpanjang "ACD". #🎜🎜##🎜🎜#Melalui kod di atas, kami menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah urutan lazim yang paling lama, dan mengesahkan ketepatan dan kebolehlaksanaan algoritma melalui contoh. Dalam aplikasi praktikal, kami boleh menggunakan algoritma ini untuk menyelesaikan pelbagai masalah pemprosesan rentetan dan meningkatkan kecekapan dan ketepatan program. #🎜🎜#

Atas ialah kandungan terperinci Analisis algoritma PHP: Bagaimana untuk menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah urutan biasa yang paling lama?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!