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.

#### 方法 1：动态规划

1. state: dp[i][j] means if substring from i to j is palindromic or not
2. init:
3. function: dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])
4. result: