回文子序列问题

概述

回文串就是正着读与反着读都一样的字符串,比如aba,a,abcba。
回文子串是指一个字符串中,连续的n个字符满足回文,比如ceabade,aba就是一个回文子串。
回文子序列是指一个字符串中,不一定连续但是其先后顺序不改变的满足回文特性的序列,比如ceabade,eabae就是一个回文子序列,且是最长的回文子序列。

最长回文子序列

动态规划思想

对于任意字符串,如果头尾字符相同,那么字符串的最长子序列等于去掉首尾的字符串的最长子序列加上首尾;如果首尾字符不同,则最长子序列等于去掉头的字符串的最长子序列和去掉尾的字符串的最长子序列的较大者。
设一个字符串str[n],lcp(0,n-1)表示str[0]到str[n-1]这个串中最长回文子序列的长度,如果str[0] == str[n-1],那么这个值就是lcp(1,n-2)+2。如果str[0]!=str[n-1],那么这个值应该是lcp(1,n-1)和lcp(0,n-2)中的较大值。
现在设一个二维数组dp[I][J]表示起点为I,终点为J的串中它的最长回文子序列的长度。
所以可以得出状态转移方程:

1
2
3
//此处的ij与IJ不同,i表示长度,j表示起点
dp[i][j+i] = dp[i+1][i+j-1]+2 (str[j] == str[i+j])
max(dp[i][i+j-1],dp[i+1][i+j]) (str[j] != str[i+j])

实现时应该有两重循环,外层循环i遍历串的长度,范围[1,n-1],内存循环j遍历起点,范围[0,n-i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lpsDp(char *str){
int dp[MAXN][MAXN];
memset(dp,0,sizeof(dp));
for(int i = 0;i<n;i++)
dp[i][i] = 1; //长度为1的字符都是回文序列
for(int i = 1;i<n;i++){ //枚举长度
for(int j = 0;j<n-i;j++){ //枚举起点
if(str[j] == str[i+j])
dp[j][i+j] = dp[j+1][i+j-1]+2;
else
dp[j][i+j] = max(dp[j][i+j-1],dp[j+1][i+j]);
}
}
return dp[0][n-1]
}

回文子序列的个数

给定一个串求回文子序列的个数,比如aba有“a”,“aa”,“b”,“aba”。对于任意字符串,如果头尾字符不相等,则字符串的回文子序列个数就等于去掉头的字符串的回文子序列个数+去掉尾的字符串的回文子序列个数-去掉头尾的字符串的回文子序列个数;
如果头尾字符相等,则字符串的回文子序列个数就等于去掉头的字符串的回文子序列个数+去掉尾的字符串的回文子序列个数+1。
状态转移方程为:

1
2
dp[j][i+j] = dp[j][j+i-1]+dp[j+1][i+j]-dp[j+1][i+j-1];   (str[j] == str[i+j])
dp[j][i+j] = dp[j][j+i-1]+dp[j+1][i+j]+1; (str[j]!=str[i+j])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int numDp(char *str){
int dp[MAXN][MAXN];
memset(dp,0,sizeof(dp));
for(int i = 0;i<n;i++)
dp[i][i] = 1; //长度为1的字符都是回文序列
for(int i = 1;i<n;i++){ //枚举长度
for(int j = 0;j<n-i;j++){ //枚举起点
if(str[j] == str[i+j])
dp[j][i+j] = dp[j][j+i-1]+dp[j+1][i+j]-dp[j+1][i+j-1];
else
dp[j][i+j] = dp[j][j+i-1]+dp[j+1][i+j]+1;
}
}
return dp[0][n-1]
}

参考资料:

blog
blog