LeetCode——最长回文子串（动态规划） C++_最长回文子串动态规划c++

题目描述取自LeetCode：

       前面的文章中介绍了本题目的暴力通过法 但是本题并不主要考察暴力算法，而是能否根据题意找到更优的解法。因此本篇博文着重介绍动态规划的解法。

        要采用动态规划算法就要首先明确dp数组中每个元素的含义是什么，这里我采用的是bool类型的二维数组，其中dp[i][j]表示的含义是字符串下标i~j的子串是否为回文串，如果是回文串则该位置的数组元素值为true，否则为false。（为保证不出现遗漏，遍历流程一定要从后往前）

        举个例子，比如现在有一个字符串"abcb"，且遍历流程为从后往前，因此矩阵的有效形状是一个上三角。该bool类型dp数组中的元素以及其对应字符串含义如下图所示：

         左图代表运行后矩阵中的值（空白位置均为false），右图代表每个值所对应的字符串子串。因此该字符串的最长子串为“bcb”。

        在本题动态规划的判断中一共需要注意符合回文子串的情况：

1）当i和j相等时子串中只有一个元素，即矩阵中的斜对角线。

2）当i和j相邻且两个元素相等时直接为回文子串。

3）当i和j对应的两个元素相等且中间子串为回文串时，该元素也为回文串。（在上图的例子中对应“bcb”，当检查到这个位置(1,3)时，两端都为‘b’则继续检查i+1和j-1(2,2)位置。由于(2,2)位置为true，则该位置也应为true）

完整代码如下：

string longestPalindrome(string s) {
        string v="";
        vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),false));
        for(int i=s.size()-1;i>=0;i--){
            for(int j=i;j<s.size();j++){
                if(i==j){//当i和j相等时为true
                    dp[i][j]=true;
                    if(j-i+1>v.size())v=s.substr(i,j-i+1);
                }
                else if(s[i]==s[j]&&j-i==1){//当i和j相邻且两个元素相等时为true
                    dp[i][j]=true;
                    if(j-i+1>v.size())v=s.substr(i,j-i+1);
                }
                else if(s[i]==s[j]&&dp[i+1][j-1]){//当i和j对应的两个元素相等且中间子串为回文串时为true
                    dp[i][j]=true;
                    if(j-i+1>v.size())v=s.substr(i,j-i+1);
                }
            }
        }
        return v;
    }