[动态规划] 六、最长回文子串

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：输入: “ABCDDCEFA”。输出: “CDDC”。
回文子串就是一个字符串从左到右读和从右到左读是完全一样的，比如 “a”、“aba”、“abba”。
条件
字符串：ABCDDCEFA

动态规划问题建模阶段

i是终止字符，j是起始字符

规律：
d[0][0] = 1
d[4][3] = 1  表示字符串从str[3]到str[4] = DD
d[5][2] = 1  表示字符串从str[2]到str[5] = CDDC

由此可见，当子串两端的字符str[i]=str[j]时，再判断去掉两端字符的子串d[i-1][j+1]是否是回文。
如果是回文，即d[i-1][j+1]=1，则d[i][j]是回文

动态规划三个重要的概念

最优子结构：
当str[8]=str[0]时，判断d[7][1]，即从str[1]到str[7]是否是回文

边界：
d[0][0] = 1
转态转移公式：
d[i][j] = 1 , i-j<3, str[i]=str[j] 因为小于3个字符一定是回文，例 A、AA、ABA
d[i][j] = d[i-1][j+1] , i-j>3, str[i]=str[j]

动态规划求解问题阶段

<?php

namespace app\index\controller;

class Index 
{
    /**
     * 动态规划（Dynamic Programming）
     * 时间复杂度：O(n²)
     * 空间复杂度：O(n²)
     */
    public function test()
    {
        $str        = 'babad';
        $palindrome = [];         // 存储“起始字符到终止字符”是否是回文，1是，0否
        $max_len    = 1;          // 存储最长回文子串长度
        $start_char = 0;          // 存储最长回文子串的起始位置
        $str_len    = strlen($str);

        // 循环字符串, i是终止字符
        for ($i=0; $i<$str_len;$i++) {

            // 循环i终止字符的每种长度情况，j是起始字符
            for ($j=0;$j<$i;$j++) {

                // 先赋初始值，供后面判断 $max_len 时使用
                $palindrome[$i][$j] = 0;

                // 字符串两头相等，根据三种情况判断是否为回文
                if ($str[$i] == $str[$j]) {
                    // 情况一：如果只有一个字符：i-j = 0；（例 A） 在数组对角线，值全为1，可写可不写
                    // 情况二：如果有两个字符：  i-j = 1；（例 AA）
                    // 情况三：如果有三个字符：  i-j = 2；（例 ABA）
                    // 这三种情况都为回文
                    if ($i-$j < 3) {
                        $palindrome[$i][$j] = 1;
                    } else {
                        // 情况四：如果子串长度大于3，判断$palindrome[i-1][j+1] 是否为1。(去两端的字符串)
                        if ($palindrome[$i-1][$j+1]) {
                            $palindrome[$i][$j] = 1;
                        }
                    }

                    // 如果是回文，且其长度比$max_len大，则更新$max_len值
                    if ($i-$j+1>$max_len && $palindrome[$i][$j]) {
                        $max_len = $i-$j+1;
                        $start_char = $j;
                    }
                }
            }
        }
        echo $max_len . "</br>";
        echo $start_char;
    }
}

参考：最长回文子串

本作品采用《CC 协议》，转载必须注明作者和本文链接