# Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Output: “bab”
Note: “aba” is also a valid answer.

### 思路3：动态规划

$P(i, j) = (P(i+1, j-1) \&\& S_i == S_j)$