Problem 15-2: More Efficient Algorithm

[cpchenpi]

There exists an $O(n^2)$ algorithm for problem 15-2.
Instead of enumerate all midpoint and solve LCS problem, we can use an interval dp method. Define dp[i, j] the answer for substring s[i..j], we can extend it (and plus one) to dp[i-1, j+1] if s[i-1]=s[j+1]. Also extend it to dp[i, j+1] and dp[i-1, j].
Actually it's just leetcode problem 516.