最长回文子串（难度：中等）

该题对应力扣网址

思路

题目分成三种情况

情况一：每一个字符都是长度为1的回文串
情况二：长度大于2的回文串：看从i到j的字符串包含的从i+1到j-1的字符串是否是回文串（动态规划思想），如果是，再比较s[i]和s[j]
情况三：长度为2的回文串

动态规划的场景变化

从上一篇博客开始，动态规划已经从显式的矩阵路径图可以直观的看到dp[i][j]中的i是横坐标，j是纵坐标这种
变成了字符串这种一维的向量
这时候，dp[i][j]中的i和j是指从下标i到下标j截取的字符串，隐含条件式i<=j

注意点

在遍历的时候，因为关键是看dp[i+1][j-1]
所以一定要保证在算dp[i][j]的时候，它的dp[i+1][j-1]其实是已经计算过的
那么也就是说，这个遍历的顺序是从下往上，从左往右

AC代码

class Solution {
public:string longestPalindrome(string s) {int m=s.length();//dp[i][j]表示从下标i到j的回文子串的最大长度vector <vector<int>> dp (m,vector<int>(m));//默认所有单个字符都是一个回文子串// memset(dp, 1, sizeof(dp));for (int i = 0; i < m; ++i) {for (int j = 0; j < m; ++j) {//情况一：每一个字符都是长度为1的回文串dp[i][j]=1;}}int max_len=1;int i1=0,j1=0;//从下往上for(int i=s.size()-1;i>=0;i--){//从左往右for(int j=i;j<s.size();j++){//当前一个字符串是回文子串时，判断当前的两边字符是否相等if(j>=1){//情况二：长度大于2的回文串if((i+1)<=(j-1)){if(dp[i+1][j-1]==(j-i-1)){if(s[i]==s[j]){dp[i][j]=j-i+1;}}}//情况三：长度为2的回文串if(j-i+1==2){if(s[i]==s[j]){dp[i][j]=j-i+1;}}if(dp[i][j]>max_len){max_len=dp[i][j];i1=i;j1=j;}}// cout<<i<<" "<<j<<" "<<i1<<" "<<max_len<<endl;}}return s.substr(i1, max_len);}
};

补充：新的代码用法

s.substr(i,len)
i是字符串的起始下标
len是截取的字符串的长度