先复习一下动态规划的三个特征：
最优子结构：就是问题的最优解包含子问题的最优解，也就是可以通过子问题的最优解，推导出问题的最优解。
无后效性：再推倒后阶段状态的时候，只关心前面阶段的状态值，而不关心这个状态是怎么推导过来的。
重复子问题：不同决策序列，到达相同阶段的时候，可能产生重复的状态。
分析：
那我们回到最长回文子串的问题上来，我们可以找到规律，我们定义两个指针i和j，代表字串在当前字符串的位置。f(i,j)代表当前字串是否是回文串f(i,j) = (s[i] == s[j]) && f(i+1,j-1),并且当j-i<3的时候,只需要比较s[i]和s[j]是否相等就可以了f(i,j) = (s[i] == s[j])。
通过以上分析，最长回文子串问题满足最优子结构（可以通过f(i+1,j-1)推导出f(i,j)）,满足无后效性（只需要知道f(i+1,j-1)的值就可以了），重复子问题。
代码：
代码如下C++
string longestPalindrome(string s) {
int n = s.length(), left = 0, right = 0;
if (n==1) return s;
vector<vector<bool>> dp(n, vector<bool>(n,false));
for (int i=n-2; i>=0; i--){
dp[i][i] = true;
for (int j=i; j<n; j++){
if (j-i < 3){
dp[i][j] = (s[i] == s[j]);
}else{
dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
}
if (dp[i][j] && (right-left < j-i)){
right = j;
left = i;
}
}
}
return s.substr(left,right);
}
