DP问题求解（三）回文字符串问题

所谓回文字符串，Palindromic Substring，指正序和倒序相同的字符串，如aba=>aba

经典的回文字符串问题

详细题目参考leetcode 5. Longest Palindromic Substring，找出一个字符串中最长的回文子串，如"babad"返回"bab"。

这道很经典的题目，可以用DP来求解，状态方程如下：

status(i,j)=(i+1 > j-1 || status(i+1,j-1) )&& (s[i] == s[j])

其中status(i,j)代表s[i]....s[j]是否是回文字符串，显然，status(i,j)是回文字符，当且仅当status(i+1,j-1)是回文字符并且s[i]==s[j]。

注意考虑为什么要添加i+1 > j-1的判断，因为当j = i + 1的时候，字符子串中只有两个字符，所以只需要对s[i]是否等于s[j]进行判断即可。

状态方程一写出来，整个题目就迎刃而解了。参考代码如下：

string longestPalindrome(string s) {
        int len = (int)s.size();
        bool status[len][len];
        memset(status,false,sizeof(status));
        for(int i = 0;i<len;i++){
            status[i][i]=true;
        }
        int maxLen = 1;
        int left = 0;
  //在这里一定要注意更新status的顺序，不然结果不正确
        for(int i = len-2;i>=0;i--){
            for(int j = i+1;j<len;j++){
                status[i][j] = ((i+1 > j-1) || status[i+1][j-1]) && (s[i] == s[j]);
                if(status[i][j] && (j-i+1)>maxLen){
                    maxLen = j-i+1;
                    left = i;
                }
            }
        }
        return s.substr(left,maxLen);
    }

回文字符串分割

详细题目参考leetcode 132. Palindrome Partitioning II，给定一个字符串，在保证分割的子串全都为回文字符串的基础上，返回最少的切割次数。

这道题还有一个初级版本，是返回所有可能的分割方式，原题参考leetcode 131. Palindrome Partitioning，这道题用普通的DFS递归思路就可以解决，具体解决办法等我写DFS系列的时候会详细介绍。如果把这道题的求解思路完全套到上面这道题中，肯定会出现超时错误，因为没有进行任何的状态存储。

所以需要想办法存储下来它的中间状态，下面要说的这种解法，虽然在leetcode上时间排名不高，但我认为比较好理解。

首先为了避免重复对字符子串是否是回文的进行判断，可以按照上一道题中的套路，用一个二维status数组存储该信息，具体步骤和上面那道题一样，就不重复介绍了。

然后使用一个一维数组dp[i]表示子串s.substr(0,i)能构成回文子字符串组合的最少切割次数，这样假设存在k(k < i)，有status[k][i]== true，那么这时候dp[i]可以写成dp[i] = dp[k-1]+1，这样的话遍历所有的k小于i，找到最小的dp[i]值，最后dp[len-1]即为所求，具体代码示例如下：

int status[1500][1500];//如果s过长，在函数内会报错
int minCut(string s) {
        int len = (int)s.size();
        int dp[len];
        dp[0]= 0;

        memset(status,false,sizeof(status));
        for(int i = 0;i<len;i++){
            status[i][i] = true;
        }

        for(int i = len-2;i>=0;i--){
            for(int j = i+1;j<len;j++){
                status[i][j] = (i+1 > j-1 || status[i+1][j-1]) && (s[i] == s[j]);
            }
        }

        for(int i = 1;i<len;i++){
            int tmp = -1;
            for(int j = 0;j<=i;j++){
                if(status[j][i]){
                    if(j == 0){
                        tmp = 0;
                        break;
                    }
                    if(tmp == -1 || dp[j-1]+1 < tmp){
                        tmp = dp[j-1]+1;
                    }
                }
            }
            dp[i] = tmp;
        }
        return dp[len-1];
    }

最长的回文子序列（Subsequence）

这里要说明一下这道题和第一道最长回文子字符串的区别，即 longest palindrome Substring 和 longest palindrome Subsequence，Substring代表子字符串，所选的字符串应该是连续的，而Subsequence子序列则不要求连续，比如"abcdef"中，Subsequence可以为"abdf"，而Substring的下标必须连续。

详细题目参考leetcode 516. Longest Palindromic Subsequence，从给定字符串中找出最长的回文子序列的长度，如输入"bbbab"，输出4（"bbbb"）。

因为没法列举出所有的回文子序列，所以可以考虑用一个二维数组保存最长回文子序列的信息，比如status(i,j)代表s[i]...s[j]之间的最长回文子序列的长度，这样可以写出状态方程：

status(i,j) = max(status(i,j-1),status(i+1,j))

status(i,j) = max(status(i,j),stauts(i+1,j-1)) s[i] == s[j]

最后返回status(0,len-1)即为所求。

参考代码如下：

int longestPalindromeSubseq(string s) {
        int len = (int)s.size();
        int status[len][len];
        memset(status,0,sizeof(status));
        for(int i = 0;i<len;i++){
            for(int j = i;j<len;j++){
                status[i][j] = 1;
            }
        }
        for(int i = len-2;i>=0;i--){
            for(int j = i+1;j<len;j++){
                status[i][j] = max(status[i+1][j],status[i][j-1]);
                if(s[i] == s[j]){
                    status[i][j] = max(status[i+1][j-1]+2,status[i][j]);
                }
            }
        }
        return status[0][len-1];
    }

复杂的计算回文子序列个数问题

同样和上面那道题一样是Subsequence问题

详细题目参考leetcode 730. Count Different Palindromic Subsequences，从给定字符串中招待所有不重复回文子序列的个数，由于结果会很大，最终结果去10^9+7的模。如输入"bccb"，返回6。

很显然暴力解肯定会出现超时错误，那应该如何使用dp来保存状态，使用status(i,j)表示s(i)...s(j)之间的回文子序列的个数，那么状态转移方程分为以下几种情况：

• 当s(i) != s(j)时，

  此时，status(i,j) = status(i+1,j)+status)i,j-1)-status(i+1,j-1)

• 当s(i) == s(j)时，

  又分为以下几种情况：

  》当s(i+1)....s(j-1)之间没有和s(i)相同的元素，则

  status(i,j)=status(i+1,j-1)*2+2

  其中的2增加的是s(i),s(j)两个组成的回文子序列

  》当s(i+1)...s(j-1)之间有且只有一个和s(i)相同的元素，则

  status(i,j)=status(i+1,j-1)*2+1

  其中的1增加的是s(i)s(j)两个组成的回文子序列，而单独的s(i)已经计算过了所以没必要再加了

  》当s(i+1)...s(j-1)中有多个和s(i)相同的元素，则

  status(i,j)=status(i+1,j-1)*2-status(low+1,high-1)

  其中low,high分别代表从左数第一个和s(i)相同的元素，high代表从右数第一个和s(j)相同的元素。减掉的中间部分是重复计算的s(i)s(low+1)...s(high-1)s(j)和s(low)s(low+1)...s(high-1)s(high)

最后需要说明的是，由于结果很可能出现溢出的情况，所以在上面每一步操作中都应该对status(i,j)进行取模操作，而不应该等到最后。又因为在运算中涉及到减操作，很可能得到负值导致结果不正确，所以在status(i,j)为负时应加上模使其变为正，详细代码如下：

int status[1000][1000];
int countPalindromicSubsequences(string S) {
        int len = (int)S.size();
        int mod = 1000000007;
        memset(status,0,sizeof(status));
        for(int i = 0;i<len;i++){
            status[i][i] = 1;
        }
        for(int i = len-2;i>=0;i--){
            for(int j = i+1;j<len;j++){
                if(S[i] != S[j]){
                    status[i][j] = (status[i][j-1] + status[i+1][j]-status[i+1][j-1])%mod;
                }
                else{
                    int low = i+1;
                    int high = j-1;
                    while(low <= high && S[low] != S[i]){
                        low++;
                    }
                    while(low <= high && S[high] != S[j]){
                        high--;
                    }
                    if(low > high){
                        status[i][j] = (2*status[i+1][j-1]+2)%mod;
                    }
                    else if(low == high){
                        status[i][j] = (2*status[i+1][j-1]+1)%mod;
                    }
                    else{
                        status[i][j] = (2*status[i+1][j-1] - status[low+1][high-1])%mod;
                    }
                }
                status[i][j] = status[i][j]<0?(status[i][j]+mod)%mod:status[i][j];
            }
        }
        return status[0][len-1];
    }