PHP algorithm analysis: How to use dynamic programming algorithm to solve the longest common subsequence problem?

PHP algorithm analysis: How to use dynamic programming algorithm to solve the longest common subsequence problem?

Dynamic Programming algorithm (Dynamic Programming) is a mathematical optimization method usually used to solve problems with overlapping sub-problems and optimal sub-structure properties. Among them, the longest common subsequence problem is a classic dynamic programming problem, which has wide applications in fields such as string processing, graph theory, and bioinformatics.

The longest common subsequence problem can be briefly described as: given two strings s1 and s2, find their longest common subsequence (Longest Common Subsequence, referred to as LCS). A subsequence of a string is a string obtained by deleting some characters from the original string without changing the order of other characters.

For example, for the strings s1 = "ABCD" and s2 = "ACDF", their longest common subsequence is "ACD".

Next, let us use PHP language to implement dynamic programming algorithm to solve the longest common subsequence problem.

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

In the above code, we define the longestCommonSubsequence function, which accepts two strings s1 and s2 and returns their final Long common subsequence.

We use a two-dimensional array$dp to record the intermediate results during the calculation process. First, we initialize the boundary condition, that is, when a string is empty, the length of the longest common subsequence is 0.

We then use two nested loops to calculate the length of the longest common subsequence. If the current characters are equal, select the length of the longest common subsequence of the two strings after removing the last character plus 1; if the current characters are not equal, select the longest common subsequence of the two strings after removing one character. The larger value of the length of the sequence.

Finally, we use the two-dimensional array of intermediate results $dp to construct the string of the longest common subsequence. Specifically, we start from the lower right corner, if the current characters are equal, add them to the longest common subsequence string, and then move the pointer to the upper left. If the current characters are not equal, the moving direction of the pointer is determined based on the results of dynamic programming calculations.

Finally, we test the example strings "ABCD" and "ACDF" and output the longest common subsequence "ACD".

Through the above code, we used dynamic programming algorithm to solve the longest common subsequence problem, and verified the correctness and feasibility of the algorithm through examples. In practical applications, we can use this algorithm to solve various string processing problems and improve the efficiency and accuracy of the program.

The above is the detailed content of PHP algorithm analysis: How to use dynamic programming algorithm to solve the longest common subsequence problem?. For more information, please follow other related articles on the PHP Chinese website!