动态规划-回文串问题——5.最长回文子串

1.题目解析

题目来源：5.最长回文子串——力扣 

测试用例 

2.算法原理

1.状态表示

判断回文子串需要知道该回文子串的首尾下标，所以需要一个二维数组且数据类型为bool类型来存储每个子字符串是否为回文子串，

即dp[i][j]:以第i个位置为起始，第j个位置为结尾的子字符串是否为回文子串

2.状态转移方程

当需要判断的子字符串长度小于3可以直接判断是否相等，相等则直接为true，反之则为false

当长度大于3时则需要向中间判断，也就是将长字符串拆分为单个字符穿与两个字符串的情况即可

3.初始化

无需初始化，因为dp表存储的值为bool类型，因此在填表的过程中就动态的将每个位置赋了值

4.填表顺序

因为需要可能用到dp[i+1][j-1]也就是二维表的左下位置，因此需要从下向上填表

5.返回值

这里的dp表每个位置存储的都是该子字符串是否为回文子串，因此需要逐个判断找出最长的回文子串并求出其起始位置与长度，然后返回该子字符串即可

3.实战代码

代码分析 

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);}
};