A4: longest palindromic substring 最长回文字串

给定一个字符串，求出其中最长的回文字串。

令N为字符串的长度，用brute force的话，总共有N²个可能的子字符串，判断每个字串是不是回文需要O(N)的时间，结果得到O(N³)的复杂度，对于长一点的输入肯定会超时。

对于长度为一个字符的字符串，其自然为回文。对于长度为2的字符串，若str[0] == str[1]，则为回文。
而对于长度为三的字符串，条件变为str[0] == str[2]，长度为四，则若str[0] == str[3]且substr(1, 2)为回文。
由此看出，若要str[0, N]为回文，必须str[1, N-1]为回文，且str[0] == str[N]。
因此用动态规划求解，子问题就是str[i, j] <- str[i+1][j-1]，得到递归方程：

dp[i, i] = true;
dp[i, i+1] == str[i] == str[i+1];
dp[i, j] = dp[i+1][j-1] && str[i] == str[j];
i, j 属于[0, N]，得到O(N²)的解法。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        bool dp[1000][1000] = { false };
        int longest, begin;
        int i, j;

        for (i=0;i<n;i++)
            dp[i][i] = true;

        longest = 1;
        begin = 0;
        for (i=0; i<n-1; i++) {
            if (s[i] == s[i+1]) {
                dp[i][i+1] = true;
                longest = 2;
                begin = i;
            }
        }

        for (j=3; j<=n; j++) {
            for (i=0; i<n-j+1; i++) {
                if (dp[i+1][i+j-2] && s[i]==s[i+j-1]) {
                    dp[i][i+j-1] = true;
                    if (longest < j) {
                        longest = j;
                        begin = i;
                    }
                }
            }
        }

        return s.substr(begin, longest);

    }
};