华为5.最长回文串

题目描述：传送门

思路与方法

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串“ababa”，如果我们已经知道“bab”是回文串，那么“ababa”一定是回文串，这是因为它的首尾两个字母都是“a”。

用DP[i][j]表示字符串s的第i个位置到第j个位置组成的串是否为回文串，根据上面的思路，可知需要判断其子串是否为回文串，即DP[i+1][j-1]是否为回文串且s[i]是否等于s[j]，因此状态转移方程为：
DP[i][j] = DP[i+1][j-1] && s[i] == s[j]
也就是说，只有s[i+1:j−1]是回文串，并且ss的第i和j个字母相同时，s[i:j] 才会是回文串。

上述情况是建立在子串长度大于2的前提之上的，还需要考虑边界条件，即子串长度为1或者2的情况。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：
长度为1时：DP[i][i] = true;
长度为2时：DP[i][i+1] = s[i] == s[i+1];

注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length() < 2)
            return s;
        vector<vector<bool>> dp(s.length(), vector<bool>(s.length(), false));
        string res;
        int pos, maxLen = 0;
        for(int l = 0; l < s.length(); l++)                //以长度为外层循环
        {
            for (int i = 0; i + l < s.length(); i++)       //依次选择每个字符作为起始字符
            {
                int j = i + l;                             //以当前字符位置+长度作为终止字符位置
                if(l == 0)
                    dp[i][j] = 1;                          //长度为0时，代表单个字符，肯定是回文串
                else if(l == 1) 
                    dp[i][j] = s[i] == s[j];               //长度为1时，如果两个字符相同，则为回文串
                else
                    dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);    //其他情况进行状态转移
                if(dp[i][j] && l + 1 > maxLen)             //如果当前是字符串，且长度最大，则保存新的位置和长度
                {
                    maxLen = l + 1;
                    pos = i;
                }
            }
        }
        res = s.substr(pos, maxLen);
        return res;
    }
};