首页 > 专题系列 > 算法分析 > 动态规划(11)-最长回文子序列
2014
04-17

动态规划(11)-最长回文子序列

给一个字符串,找出它的最长的回文子序列的长度。例如,如果给定的序列是“BBABCBCAB”,则输出应该是7,“BABCBAB”是在它的最长回文子序列。 “BBBBB”和“BBCBB”也都是该字符串的回文子序列,但不是最长的。注意和最长回文子串的区别(参考:最长回文串)!这里说的子序列,类似最长公共子序列LCS( Longest Common Subsequence)问题,可以是不连续的。这就是LPS(Longest Palindromic Subsequence)问题。

最直接的解决方法是:生成给定字符串的所有子序列,并找出最长的回文序列,这个方法的复杂度是指数级的。下面来分析怎么用动态规划解决。

1)最优子结构

假设 X[0 ... n-1]  是给定的序列,长度为n.  让 L(0,n-1) 表示 序列 X[0 ... n-1] 的最长回文子序列的长度。

1. 如果X的最后一个元素和第一个元素是相同的,这时:L(0, n-1) = L(1, n-2) + 2 ,  还以 “BBABCBCAB” 为例,第一个和最后一个相同,因此 L(1,n-2) 就表示蓝色的部分。

2. 如果不相同:L(0, n-1) = MAX ( L(1, n-1) ,  L(0, n-2) )。 以”BABCBCA” 为例,L(1,n-1)即为去掉第一个元素的子序列,L(0, n-2)为去掉最后一个元素。

有了上面的公式,可以很容易的写出下面的递归程序:

#include<stdio.h>
#include<string.h>
int lps(char *seq, int i, int j)
{
   //一个元素即为1
   if (i == j)
     return 1;
   if(i > j) return 0; //因为只计算序列 seq[i ... j]

   // 如果首尾相同
   if (seq[i] == seq[j])
      return lps (seq, i+1, j-1) + 2;

   // 首尾不同
   return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}

/* 测试 */
int main()
{
    char seq[] = "acmerandacm";
    int n = strlen(seq);
    printf ("The lnegth of the LPS is %d", lps(seq, 0, n-1));
    getchar();
    return 0;
}

Output: The lnegth of the LPS is 5 (即为: amama)

重叠子问题

画出上面程序的递归树(部分),已一个长度为6 的字符串为例:

               L(0, 5)
             /        \ 
            /          \  
        L(1,5)          L(0,4)
       /    \            /    \
      /      \          /      \
  L(2,5)    L(1,4)  L(1,4)  L(0,3)

可见有许多重复的计算,例如L(1,4)。该问题符合动态规划的两个主要性质: 重叠子问题最优子结构 

下面通过动态规划的方法解决,通过自下而上的方式打表,存储子问题的最优解。

int lpsDp(char * str,int n){
	int dp[n][n], tmp;
	memset(dp,0,sizeof(dp));
	for(int i=0; i<n; i++) dp[i][i] = 1;
	// i 表示 当前长度为 i+1的 子序列
	for(int i=1; i<n; i++){
		tmp = 0;
		//考虑所有连续的长度为i+1的子串. 该串为 str[j, j+i]
		for(int j=0; j+i<n; j++){
			//如果首尾相同
			if(str[j] == str[j+i]){
				tmp = dp[j+1][j+i-1] + 2;
			}else{
				tmp = max(dp[j+1][j+i],dp[j][j+i-1]);
			}
			dp[j][j+i] = tmp;
		}
	}
	//返回串 str[0][n-1] 的结果
	return dp[0][n-1];
}

该算法的时间复杂度为O(n^2)。其实这个问题和 最长公共子序列 问题有些相似之处,我们可以对LCS算法做些修改,来解决此问题:

1) 对给定的字符串逆序 存储在另一个数组 rev[] 中

2) 再求这两个 字符串的 LCS的长度

时间复杂度也为 O(n^2)。

参考:http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/


  1. 思路一看就是错的,试一下“badb”,递归程序输出3,dp的代码更是懒得试了

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。