PHP algorithm analysis: How to use dynamic programming algorithm to solve the longest palindrome substring problem?

PHP algorithm analysis: How to use dynamic programming algorithm to solve the longest palindrome substring problem?

Dynamic Programming (Dynamic Programming) is a commonly used algorithm idea that can solve many complex problems. One of them is the longest palindrome substring problem, which is to find the length of the longest palindrome substring in a string. This article will introduce how to use PHP to write a dynamic programming algorithm to solve this problem, and provide specific code examples.

First define the longest palindrome substring. A palindrome string refers to a string that reads the same forward and backward, while a palindrome substring is a continuous palindrome string in the original string. For example, in the string "level", "eve" is a palindrome substring.

To solve the longest palindrome substring problem, we can use the idea of ​​dynamic programming algorithm. Specifically, we can use a two-dimensional array dp to represent whether each substring in the string is a palindrome string. dpi indicates whether the substring formed from the i-th character to the j-th character is a palindrome string. If dpi is true, then the substring from the i-th character to the j-th character is a palindrome substring.

Next, we need to find the state transition equation, that is, how to deduce the value of dpi 1 based on the known dpi. According to the properties of palindrome strings, we know that if dpi is true, then the value of dpi 1 depends on whether the i 1-th character and j 1-th character are equal. If they are equal, then you only need to determine whether the substring from the i 1st character to the jth character is a palindrome string, that is, the value of dpi 1. Otherwise, dpi 1 is false.

With the state transition equation, we can start writing PHP code to solve the longest palindrome substring problem.

function longestPalindrome($s) {
    $n = strlen($s);
    $dp = array_fill(0, $n, array_fill(0, $n, false)); // 初始化dp数组，默认都为false

    // 初始化最长回文子串的起始位置和长度
    $start = 0;
    $maxLen = 1;

    // 单个字符都是回文子串
    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = true;
    }

    // 根据状态转移方程计算dp数组
    for ($j = 1; $j < $n; $j++) {
        for ($i = 0; $i < $j; $i++) {
            if ($s[$i] == $s[$j]) {
                if ($j - $i <= 2 || $dp[$i + 1][$j - 1]) {
                    $dp[$i][$j] = true;
                    if ($j - $i + 1 > $maxLen) {
                        $maxLen = $j - $i + 1;
                        $start = $i;
                    }
                }
            }
        }
    }

    return substr($s, $start, $maxLen); // 返回最长回文子串
}

// 测试示例
$str = "babad";
echo longestPalindrome($str);

In the above code, we define a function longestPalindrome to solve the longest palindrome substring problem. The function accepts a string $s as a parameter and returns the longest palindrome substring. In the function, we first initialize the dp array and mark individual characters as palindrome substrings. Then, calculate the dp array according to the state transition equation. Finally, we return the longest palindromic substring based on the starting position and length.

In the sample code, our test string is "babad", and the output result is "bab", which is the longest palindrome substring.

By using dynamic programming algorithm, we can solve the longest palindrome substring problem efficiently. I hope this article will be helpful in understanding and applying dynamic programming algorithms.

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