LeetCode 最长回文子串：动态规划算法详解与 Python 实践

本文深入探讨如何使用动态规划解决 LeetCode 最长回文子串问题。通过分析最优子结构、边界与状态转移公式，并提供 Python 代码实现，帮助你理解动态规划算法的精髓。

核心内容

问题来自于我在leetcode刷到的一个找最长回文子串的问题，自己使用了简单的暴力搜索，Google之后发现了利用动态规划解决该问题，感觉很巧妙，记录一下。

简述

• 动态规划就是把一个复杂问题分阶段简化，逐步化简为简单问题的过程，动态规划中包含三个重要的概念：最优子结构,边界，状态转移公式。
• 分析：基本思路是对任意字符串，如果头和尾相同，那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。如果头和尾不同，那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。

P[i,j]: 表示第i到第j个字符的回文子串数 
dp[i,i]=1
dp[i,j]=dp[i+1,j−1]+2 if s[i]=s[j]
dp[i,j]=max(dp[i+1,j],dp[i,j−1]) if s[i]!=s[j]

代码实现

def longestPalindrome(self, s: str) -> str:
    start=0
    maxstr=0
    for i in range(len(s)):
        if i-maxstr>=1 and s[i-maxstr-1:i+1]==s[i-maxstr-1:i+1][::-1]:
            start = i-maxstr-1
            maxstr+=2
            continue
        if  i-maxstr>=0 and s[i-maxstr:i+1]==s[i-maxstr:i+1][::-1]:
            start = i-maxstr
            maxstr+=1
    return s[start:start+maxstr]

参考链接

看动画轻松理解「递归」与「动态规划」 Longest Palindromic Substring 最长回文子串 Python 四种解法