秒懂【最长回文子串】！动态规划一步步拆解。

1.思路

对于回文，定义两个变量i和j，都指向字符串对应的字符。i和j变量回文判断指向如下图所示。刚开始的时候i、变量都指向同一个字符，之后i尝试向左移动，j变量尝试向右移动。

因此变量 i 取值范围（从最后一个元素到第0个元素，从后往前遍历）：arr[len(arr),0,-1]；遍历 j 取值范围（从i开始到最后一个元素）：arr[j:len(arr)]。

alt

只有arr[i]==arr[j]时，才有可能存在回文: arr[i:j]区间是否为回文依赖与arr[i+1:j-1]的子区间是否为回文即：dp[i][j]依赖于dp[i+1][j-1]

根据i、j变量的取值范围，dp[i][j]二维数组是从左下角往右上角推导的。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param A string字符串
# @return int整型
#
class Solution:
    def getLongestPalindrome(self, arr: str) -> int:
        # write code here
        # 1. 定义状态.   dp[i][j]: 字符串arr[i:j] 区间内是否为回文子串
        dp = [[False] * len(arr) for _ in range(len(arr))]
        # 2. 初始化边界条件：
        # dp[i][j] = false
        palindrome_len = 0  # 最长回文长度
        palindrome_str = ""  # 最长回文子串
        # 3. 确定递推公式：
        for i in range(len(arr) - 1, -1, -1):
            for j in range(i, len(arr)):
                if arr[i] == arr[j]:
                    if i == j:  # 只有1个字符的情况
                        dp[i][j] = True
                    elif j == i + 1:  # 有2个字符的情况
                        dp[i][j] = True
                    elif dp[i + 1][j - 1]:  # 超过2个字符的情况
                        dp[i][j] = True
                # 更新回文子串长度
                if dp[i][j] and (j - i + 1) > palindrome_len:
                    palindrome_len = j - i + 1
                    palindrome_str = arr[i : j + 1]  # 最长回文字符串是连续的，因此可以通过截取获得
        # 4.输出结果
        print(palindrome_str)
        return palindrome_len

2.2 Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String str) {
        // write code here
        //1.定义状态.     dp[i][j]:字符串str[i:j]区间内是否为回文子串
        boolean[][] dp = new boolean[str.length()][str.length()];
        //2.初始化边界条件：
        // dp[i][j]=false
        int palindromeLen = 0;//最长回文长度
        String palindromeStr = "";
        //3.确定递推公式：
        for (int i = str.length() - 1; i >= 0; i--) {
            for (int j = i; j < str.length(); j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    if (i == j) { //只有1个字符的情况
                        dp[i][j] = true;
                    } else if (j == i + 1) {  //有2个字符的情
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {//超过2个字符的情况
                        dp[i][j] = true;
                    }
                }
                //更新回文子串长度
                if (dp[i][j] && (j - i + 1) > palindromeLen) {
                    palindromeLen = j - i + 1;
                    palindromeStr = str.substring(i,
                                                  j + 1); //最长回文字符串是连续的，因此可以通过截取获得
                }

            }
        }
        //4.输出结果
        System.out.println(palindromeStr);
        return palindromeLen;
    }
}

2.3 Go代码

package main

import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param A string字符串
 * @return int整型
 */
func getLongestPalindrome(arr string) int {
	// write code here
	//1.定义状态.	  dp[i][j]:字符串arr[i:j]区间内是否为回文子串
	dp := newArray(len(arr), len(arr))
	//2.初始化边界条件：
	//dp[i][j]=false
	palindromeLen := 0  //最长回文长度
	palindromeStr := "" //最长回文子串
	//3.确定递推公式：
	for i := len(arr) - 1; i >= 0; i-- {
		for j := i; j < len(arr); j++ {
			if arr[i] == arr[j] {
				if i == j { //只有1个字符的情况
					dp[i][j] = true
				} else if j == i+1 { //有2个字符的情况
					dp[i][j] = true
				} else if dp[i+1][j-1] { //超过2个字符的情况
					dp[i][j] = true
				}
			}
			//更新回文子串长度
			if dp[i][j] && (j-i+1) > palindromeLen {
				palindromeLen = j - i + 1
				palindromeStr = arr[i : j+1]
			}
		}
	}
	//4.输出结果
	fmt.Println(palindromeStr)
	return palindromeLen
}

// 创建一个 m行n列的矩阵（二维数组）
func newArray(m int, n int) [][]bool {
	arr := make([][]bool, m)
	for i := 0; i < m; i++ {
		arr[i] = make([]bool, n)
	}
	return arr
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构