1.題目解析

題目來源：5.最長回文子串——力扣?

測試用例?

2.算法原理

1.狀態(tài)表示

判斷回文子串需要知道該回文子串的首尾下標(biāo)，所以需要一個(gè)二維數(shù)組且數(shù)據(jù)類型為bool類型來存儲每個(gè)子字符串是否為回文子串，

即dp[i][j]:以第i個(gè)位置為起始，第j個(gè)位置為結(jié)尾的子字符串是否為回文子串

2.狀態(tài)轉(zhuǎn)移方程

當(dāng)需要判斷的子字符串長度小于3可以直接判斷是否相等，相等則直接為true，反之則為false

當(dāng)長度大于3時(shí)則需要向中間判斷，也就是將長字符串拆分為單個(gè)字符穿與兩個(gè)字符串的情況即可

3.初始化

無需初始化，因?yàn)閐p表存儲的值為bool類型，因此在填表的過程中就動態(tài)的將每個(gè)位置賦了值

4.填表順序

因?yàn)樾枰赡苡玫絛p[i+1][j-1]也就是二維表的左下位置，因此需要從下向上填表

5.返回值

這里的dp表每個(gè)位置存儲的都是該子字符串是否為回文子串，因此需要逐個(gè)判斷找出最長的回文子串并求出其起始位置與長度，然后返回該子字符串即可

3.實(shí)戰(zhàn)代碼

代碼分析?

class Solution {
public:string longestPalindrome(string s) {int n = s.size();vector<vector<bool>> dp(n,vector<bool>(n));int len = 1,begin = 0;for(int i = n - 1;i >= 0;i--){for(int j = i;j < n;j++){if(s[i] == s[j]){dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;}if(dp[i][j] && j - i + 1 > len){len = j - i + 1;begin = i;}}}   return s.substr(begin,len);}
};

?