问题
给定一个字符串 S，找出其最长的回文子字符串。S 的最大长度为1000。
举例
输入："babad"
输出："bab"
（注："aba" 也是一个正确的结果）
思路
若长度为 L 的字符串为回文，则去掉首尾的字符，长度为 L-2 的字符串也为回文。
即全局最优解包含局部最优解。
最小子问题
- 单个字符独立成为一个回文字符串
- 相邻的两个相同字符，是一个回文字符串
递推方程
设置一个 L*L 的矩阵 D，D[i][j] 的值为 ture 或 false， 表示从 i 起始 j 终止的字符串是否为回文。
则有：
D[i][j] = (D[i] === D[j]) && D[i+1][j-1]
（若第 i 个字符与第 j 个字符相同，且从 i+1 起始 j-1 终止的字符串为回文，则有从 i 起始 j 终止的字符串也为回文）
解法
function handleStr(str) {
let L = str.length
let d = []
for(let i=0;i<L;i++) { // 初始化矩阵D，且先将最小子问题1的情况都设置为true
let arr = []
arr[i] = true
d[i] = arr
}
let maxLen = 1,
resIndex = 0
for(let i=0;i<L;i++) { // 再将最小子问题2的情况都设置为true
if(str[i] === str[i+1]) {
d[i][i+1] = true
if(maxLen < 2) { // 如果最小子问题成立，则最长回文字符串为2
maxLen = 2
resIndex = i
}
}
}
for(let len=3;len<=L;len++) { // 从长度为3开始逐渐增长的检查回文字符串
for(let i=0;i<L-len+1;i++) { // 从第0个位置开始，依据最小子问题1、2来依次检查回文字符串
if(str[i] === str[i+len-1] && d[i+1][i+len-2]) {
d[i][i+len-1] = true
if(len > maxLen) { // 满足条件时，保存回文字符串长度和起始位置
maxLen = len
resIndex = i
}
}
}
}
return str.substr(resIndex, maxLen)
}
