【題目描述】
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of Sis 1000, and there exists one unique longest palindromic substring.
給出一個字符串（假設(shè)長度最長為1000），求出它的最長回文子串，你可以假定只有一個滿足條件的最長回文串。
【題目鏈接】
www.lintcode.com/en/problem/longest-palindromic-substring/
【題目解析】
此題可使用區(qū)間類動態(tài)規(guī)劃。
用dp[i][j]來存DP的狀態(tài)，需要較多的額外空間: Space O(n^2)
DP的4個要素
狀態(tài)：
dp[i][j]: s.charAt(i)到s.charAt(j)是否構(gòu)成一個Palindrome
轉(zhuǎn)移方程：
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])
初始化：
dp[i][j] = true when j - i <= 2
結(jié)果：
找maxLen = j - i + 1;，并得到相應(yīng)longest substring：longest = s.substring(i, j + 1);
【參考答案】
