【动态规划】回文子序列个数

Description

给定一个字符序列，求这个序列中回文子序列的个数。

Input

包含多组用例，每个用例为一行字符序列（只含有字母和数字，不包含空格，字符串长度小于100）。

Output

输出该字符序列中回文子序列的个数。

Sample Input

aaaa aaba

Sample Output

15 10

HINT

对于样例2，有如下回文子序列（为便于观察，我们另字符序列为a1 a2 b a3）：

a1 a2

a1 a3

a2 a3

a1 b a3

a2 b a3

a1 a2 a3

思路方法与代码均转载自 http://www.cnblogs.com/AndyJee/p/4465696.html （侵删）

参考 http://blog.csdn.net/piaocoder/article/details/51066568 （侵删）

思路

动态规划思想

对于任意字符串，如果头尾字符不相等，则字符串的回文子序列个数就等于去掉头的字符串的回文子序列个数+去掉尾的字符串的回文子序列个数-去掉头尾的字符串的回文子序列个数；如果头尾字符相等，那么除了上述的子序列个数之外，还要加上首尾相等时新增的子序列个数，1+去掉头尾的字符串的回文子序列个数，1指的是加上头尾组成的回文子序列，如aa，bb等。

因此动态规划的状态转移方程为：

设字符串为str，长度为n，p[i][j]表示第i到第j个字符间的最长子序列的长度（i<=j），则：

状态初始条件：dp[i][i]=1 （i=0：n-1）

状态转移方程：dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] if（str[i]！=str[j]）

dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]+dp[i+1][j-1]+1=dp[i+1][j] + dp[i][j-1]+1 if （str[i]==str[j]）

对任意字符串，如果头和尾相同，那么它的最长回文子序列一定是去头去尾之后的部分的最长回文子序列加上头和尾。如果头和尾

不同，那么它的最长回文子序列是去头的部分的最长回文子序列和去尾的部分的最长回文子序列的较长的那一个。

设字符串为str，dp(i,j)表示str[i..j]的最长回文子序列。

状态转移方程如下：

当i > j时，dp[i,j]= 0。

当i = j时，dp[i,j] = 1。

当i < j并且str[i] == str[j]时，dp[i][j] = dp[i+1][j-1]+2;

当i < j并且str[i] ≠ str[j]时，dp[i][j] = max(dp[i][j-1],dp[i+1][j]);

注意如果i+1 == j并且str[i] == str[j]时，dp[i][j] = dp[i+1][j-1]+2 = dp[j,j-1]+2 = 2，这就是“当i > j时f(i,j)=0”的好处。

由于dp[i][j]依赖i+1，所以循环计算的时候，第一维必须倒过来计算，从len-1到0。

最后，s的最长回文子序列长度为dp[0][len-1]。

代码（未ac)

#include <iostream>
#include <vector>
using namespace std;

int NumOfPalindromeSubSequence(string str){
    int len=str.length();
    vector<vector<int> > dp(len,vector<int>(len));

    for(int j=0;j<len;j++){
        dp[j][j]=1;
        for(int i=j-1;i>=0;i--){
            dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
            if(str[i]==str[j])
                dp[i][j]+=1+dp[i+1][j-1];
        }
    }
    return dp[0][len-1];
}

int main()
{
    string str;
    int num;
    while(cin>>str){
        num=NumOfPalindromeSubSequence(str);
        cout<<num<<endl;
    }
    return 0;
}

于是向学霸copy了一段能ac的代码如下

#include <iostream>//用来求最长回文子序列的长度
#include <string.h>
#include <vector>
#include <cstdlib>
#include <algorithm>
#define MAXSIZE 105
#define vi vector<int> 
#define vvi vector<vector<int> > 
#define vll vector<long long> 
#define vvll vector<vector<long long> > 
using namespace std;

long LengthofLongestPalindlrome(char ch[]) {
    long len = strlen(ch);
    vvi dp(len, vi(len));

    for (int j = 0; j < len; j++) {
        dp[j][j] = 1;//开始漏掉了，结果错误
        for (int i = j - 1; i >= 0; i--) {
            if (ch[i] == ch[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            }
            else
            {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][len - 1];

}

long long NumOfPalinrome(char ch[]) {
    long long len = (long long)strlen(ch);
    vvll dp(len, vll(len));

    for (int j = 0; j < len; j++) {
        dp[j][j] = 1;//开始漏掉了，结果错误
        for (int i = j - 1; i >= 0; i--) {            
            dp[i][j] = dp[i + 1][j]+dp[i][j-1] -dp[i+1][j-1];
            if (ch[i] == ch[j]) 
            {
                dp[i][j] +=1+ dp[i + 1][j-1];//注意这里！！！
            }
        }
    }
    return dp[0][len - 1];

}

int main() {
    //string str;
    char ch[MAXSIZE];

    //int dp[MAXSIZE][MAXSIZE];
    while (cin>>ch)
    //while(scanf_s("%s",ch)!=EOF)
    {
        //int length = LengthofLongestPalindlrome(ch);
        long long length2 = NumOfPalinrome(ch);
        //cout << length << endl;
        cout << length2 << endl;
    }
    return 0;
}