动态规划问题，用数组保存所有子串的回文状态，用 l 表示左游标，r 表示右游标，那么dp[l][r] 中的值即代表 l 到 r 这个长度的子串是否回文。
状态有两种判断条件，一种是 如果 l == r + 1 即子串长度为2， 那么只要这两个字符相等就是回文；
另外一种则是不但要求左端和右端字符相等，还要求嵌套的子串为回文，即要求 dp[l+1][r-1] 必须为 true;
class Solution { public String longestPalindrome(String s) { int start=0,end=0; Boolean[][] dp = new Boolean[s.length()][s.length()]; if(s.length()<2) return s; for(int r=0;r<s.length();r++){ dp[r][r] = true; for(int l=0;l<r;l++){ if(l+1==r){ dp[l][r] = (s.charAt(l)==s.charAt(r)); } else{ dp[l][r] = (dp[l+1][r-1] && (s.charAt(l)==s.charAt(r))); } if(dp[l][r] && r-l>end-start){ end=r; start=l; } } } return s.substring(start, end+1); } }
class Solution: def longestPalindrome(self, s: str) -> str: if len(s) <2: return s dp = [[False for i in range(len(s))] for j in range(len(s))] start = 0 end = 0 for r in range(len(s)): dp[r][r] = True for l in range(r): if l+1==r: dp[l][r] = (s[l] == s[r]) else: dp[l][r] = (dp[l+1][r-1] and (s[l] == s[r])) if(dp[l][r] and (r-l > end-start)): end = r start = l return s[start:end+1]
原文：https://www.cnblogs.com/huangzengrui/p/12342949.html