给定一个字符串 s，找到 s 中最长的回文子串。可以假设 s 的最大长度为 1000
样例
输入 xabbbbbabbacd
输出 abbbbba
class Solution { public: string longestPalindrome(string s) { int n=s.size(); if(n==0) return s; bool dp[n][n]; memset(dp,0,sizeof(dp)); int maxlen=1,start=0; for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { if(i-j<2) dp[i][j]=(s[i]==s[j]); else dp[i][j]=(s[i]==s[j]&&dp[i-1][j+1]==1); if(dp[i][j]&&maxlen<i-j+1) { maxlen=i-j+1; start=j; } } } return s.substr(start,maxlen); } };
此题的状态转移方程是 dp[i][j]=s[i]==s[j]&&dp[i-1][j+1]==1
和之前所做的题不同，按照以往，会设定状态i,j为在：区间i,j内字符的最长回文长度为dp[i][j]，或者设定以i为结尾字符串的最长回文长度为dp[i],但是这样找不出递推式。
可以转换思路为，设定状态i,j为：以i为起点j为终点的字符串是否为回文dp[i][j]=1或dp[i][j]=0，若s[i]=s[j]并且dp[i-1][j+1]是回文，则dp[i][j]是回文.
maxlen初始化为1，若dp[i][j]是回文，则maxlen=i-j+1，start=j。
如果用双递归找出所有子串再判断是否为回文，由于没有状态转移方程，所以子串会被多次重复计算。
【总结】1.dp的值可以bool表示0、1，用下标表示位置。
2.动态规划不一定用到递归，用循环也可以。
原文：https://www.cnblogs.com/apo2019/p/10765814.html