题目：
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
代码：
class Solution {
public:
string longestPalindrome(string s) {
const size_t len = s.length();
// initialize dp matrix
bool dp[len][len];
std::fill_n(&dp[][], len*len, false);
dp[][] = true;
for ( size_t i = ; i < len; ++i )
{
dp[i][i] = true;
dp[i][i-] = true;
}
// dp process
size_t left = ;
size_t longest_palindrome = ;
for ( size_t k = ; k <= len; ++k )
{
for ( size_t i = ; i <= len-k; ++i )
{
if ( dp[i+][i+k-] && s[i]==s[i+k-] )
{
dp[i][i+k-] = true;
if ( longest_palindrome < k )
{
left = i;
longest_palindrome = k;
}
}
}
}
return s.substr(left,longest_palindrome);
}
};
tips:
采用动态规划思路，时间复杂度O(n²)。代码并不是最优的，但是相对简洁的（不用考虑奇数偶数的情况）。
判断一个子串是否是回文可以用其“掐头去尾”后的子子串是来判断：
a. 子子串是回文
b. 头等于尾
同时满足a,b则一定是回文；否则，一定不是回文。
这里设定一个dp[][]数组：dp[i][j]=true表示i到j这个子串是回文，dp[i][j]=false表示i到j这个子串不是回文。
对dp数组初始化时候需要注意两点：
(1)
显然dp[i][i]表示单个元素，都是回文，初始化为true。
(2)
dp[i][i-1]这种情况按理说是不存在的（因为左边的index不能大于右边的index），但是当k=2的时候，判断相邻两个字符是否构成回文的时候
有“dp[i+1][i+k-2]”这个情况，显然dp[i+1][i]，此时这个判断其实是不起作用的，只用判断相邻两个元素相等即可；但是为了代码的简洁（都在一个循环中写下），强制令dp[1][0]、dp[2][1]、...、dp[len-1][len-2]都为true。
这里第一层循环k代表可能回文的长度（从2起），第二层循环i代表回文开始的位置。这里有一点要注意，就是k是可以取到len这个值的（即整个字符串就是一个大回文）；并且，i是可以取到len-k的（因为最后一个字符的下标是len-1到len-k长度正好是k）。这两个边界细节要注意。
另，还有大Manacher算法，可以做到O(n)时间复杂度。以后再研究一下。
================================================
第二次过这道题，记得还用动归；但是具体指针下标迭代还需要考虑清楚。
class Solution {
public:
string longestPalindrome(string s) {
const int len = s.size();
bool dp[len][len];
std::fill_n(&dp[][], len*len, false);
for ( int i=; i<len; ++i ) dp[i][i]=true;
int l = ;
int r = ;
for ( int i=; i<len; ++i )
{
for ( int j=; j<i; ++j )
{
if ( i-j< )
{
dp[j][i] = s[i]==s[j];
if ( dp[j][i] && i-j>r-l )
{
l = j;
r = i;
}
}
else
{
dp[j][i] = dp[j+][i-] && s[i]==s[j];
if ( dp[j][i] && i-j>r-l )
{
l = j;
r = i;
}
}
}
}
return s.substr(l,r-l+);
}
};