本文概述
给定一个序列, 找到其中最长回文子序列的长度。
作为另一个示例, 如果给定序列为" BBABCBCAB", 则输出应为7, 因为" BABCBAB"是其中最长的回文子序列。 " BBBBB"和" BBCBB"也是给定序列的回文序列, 但不是最长的。
这个问题的幼稚解决方案是生成给定序列的所有子序列, 并找到最长的回文子序列。该解决方案在时间复杂度方面是指数的。让我们看看这个问题如何同时具有动态编程(DP)问题的两个重要属性, 以及如何使用动态编程来有效地解决。
1)最佳子结构:
令X [0..n-1]为长度n的输入序列, L(0, n-1)为X [0..n-1]的最长回文子序列的长度。
如果X的最后一个字符和第一个字符相同, 则L(0, n-1)= L(1, n-2)+ 2。
否则L(0, n-1)= MAX(L(1, n-1), L(0, n-2))。
以下是处理所有情况的通用递归解决方案。
//Every single character is a palindrome of length 1
L(i, i) = 1 for all indexes i in given sequence
//IF first and last characters are not same
If (X[i] != X[j]) L(i, j) = max{L(i + 1, j), L(i, j - 1)}
//If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2
//If there are more than two characters, and first and last
//characters are same
Else L(i, j) = L(i + 1, j - 1) + 2
2)重叠子问题
以下是LPS问题的简单递归实现。该实现仅遵循上述递归结构。
C++
//C++ program of above approach
#include<bits/stdc++.h>
using namespace std;
//A utility function to get max of two integers
int max ( int x, int y) { return (x> y)? x : y; }
//Returns the length of the longest palindromic subsequence in seq
int lps( char *seq, int i, int j)
{
//Base Case 1: If there is only 1 character
if (i == j)
return 1;
//Base Case 2: If there are only 2
//characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
//If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;
//If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}
/* Driver program to test above functions */
int main()
{
char seq[] = "lsbin" ;
int n = strlen (seq);
cout <<"The length of the LPS is "
<<lps(seq, 0, n-1);
return 0;
}
//This code is contributed
//by Akanksha Rai
C
//C program of above approach
#include<stdio.h>
#include<string.h>
//A utility function to get max of two integers
int max ( int x, int y) { return (x> y)? x : y; }
//Returns the length of the longest palindromic subsequence in seq
int lps( char *seq, int i, int j)
{
//Base Case 1: If there is only 1 character
if (i == j)
return 1;
//Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
//If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;
//If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}
/* Driver program to test above functions */
int main()
{
char seq[] = "lsbin" ;
int n = strlen (seq);
printf ( "The length of the LPS is %d" , lps(seq, 0, n-1));
getchar ();
return 0;
}
Java
//Java program of above approach
class GFG {
//A utility function to get max of two integers
static int max( int x, int y) {
return (x> y) ? x : y;
}
//Returns the length of the longest palindromic subsequence in seq
static int lps( char seq[], int i, int j) {
//Base Case 1: If there is only 1 character
if (i == j) {
return 1 ;
}
//Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2 ;
}
//If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1 , j - 1 ) + 2 ;
}
//If the first and last characters do not match
return max(lps(seq, i, j - 1 ), lps(seq, i + 1 , j));
}
/* Driver program to test above function */
public static void main(String[] args) {
String seq = "lsbin" ;
int n = seq.length();
System.out.printf( "The length of the LPS is %d" , lps(seq.toCharArray(), 0 , n - 1 ));
}
}
Python3
# Python 3 program of above approach
# A utility function to get max
# of two egers
def max (x, y):
if (x> y):
return x
return y
# Returns the length of the longest
# palindromic subsequence in seq
def lps(seq, i, j):
# Base Case 1: If there is
# only 1 character
if (i = = j):
return 1
# Base Case 2: If there are only 2
# characters and both are same
if (seq[i] = = seq[j] and i + 1 = = j):
return 2
# If the first and last characters match
if (seq[i] = = seq[j]):
return lps(seq, i + 1 , j - 1 ) + 2
# If the first and last characters
# do not match
return max (lps(seq, i, j - 1 ), lps(seq, i + 1 , j))
# Driver Code
if __name__ = = '__main__' :
seq = "lsbin"
n = len (seq)
print ( "The length of the LPS is" , lps(seq, 0 , n - 1 ))
# This code contributed by Rajput-Ji
C#
//C# program of the above approach
using System;
public class GFG{
//A utility function to get max of two integers
static int max( int x, int y) {
return (x> y) ? x : y;
}
//Returns the length of the longest palindromic subsequence in seq
static int lps( char []seq, int i, int j) {
//Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
//Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
//If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
//If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above function */
public static void Main() {
String seq = "lsbin" ;
int n = seq.Length;
Console.Write( "The length of the LPS is " +lps(seq.ToCharArray(), 0, n - 1));
}
}
//This code is contributed by Rajput-Ji
PHP
<?php
//PHP program of above approach
//Returns the length of the longest
//palindromic subsequence in seq
function lps( $seq , $i , $j )
{
//Base Case 1: If there is
//only 1 character
if ( $i == $j )
return 1;
//Base Case 2: If there are only 2
//characters and both are same
if ( $seq [ $i ] == $seq [ $j ] && $i + 1 == $j )
return 2;
//If the first and last characters match
if ( $seq [ $i ] == $seq [ $j ])
return lps ( $seq , $i + 1, $j - 1) + 2;
//If the first and last characters
//do not match
return max(lps( $seq , $i , $j - 1), lps( $seq , $i + 1, $j ));
}
//Driver Code
$seq = "lsbin" ;
$n = strlen ( $seq );
echo "The length of the LPS is " .
lps( $seq , 0, $n - 1);
//This code is contributed by ita_c
?>
输出如下:
The length of the LPS is 5
考虑到以上实现, 以下是具有所有不同字符的长度为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)被求解两次。如果我们绘制完整的递归树, 则可以看到有很多子问题可以一次又一次地解决。由于再次调用了相同的子问题, 因此此问题具有"重叠子问题"属性。因此, LPS问题具有两个属性(请参阅这个和这个)的动态编程问题。像其他典型的动态编程(DP)问题, 可以通过自下而上的方式构造临时数组L [] []来避免相同子问题的重新计算。
动态编程解决方案
C++
//A Dynamic Programming based C++ program for LPS problem
//Returns the length of the longest palindromic subsequence in seq
#include<stdio.h>
#include<string.h>
//A utility function to get max of two integers
int max ( int x, int y) { return (x> y)? x : y; }
//Returns the length of the longest palindromic subsequence in seq
int lps( char *str)
{
int n = strlen (str);
int i, j, cl;
int L[n][n]; //Create a table to store results of subproblems
//Strings of length 1 are palindrome of lentgh 1
for (i = 0; i <n; i++)
L[i][i] = 1;
//Build the table. Note that the lower diagonal values of table are
//useless and not filled in the process. The values are filled in a
//manner similar to Matrix Chain Multiplication DP solution (See
//https://www.lsbin.org/matrix-chain-multiplication-dp-8/). cl is length of
//substring
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (str[i] == str[j] && cl == 2)
L[i][j] = 2;
else if (str[i] == str[j])
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}
/* Driver program to test above functions */
int main()
{
char seq[] = "GEEKS FOR GEEKS" ;
int n = strlen (seq);
printf ( "The length of the LPS is %d" , lps(seq));
getchar ();
return 0;
}
Java
//A Dynamic Programming based Java
//Program for the Egg Dropping Puzzle
class LPS
{
//A utility function to get max of two integers
static int max ( int x, int y) { return (x> y)? x : y; }
//Returns the length of the longest
//palindromic subsequence in seq
static int lps(String seq)
{
int n = seq.length();
int i, j, cl;
//Create a table to store results of subproblems
int L[][] = new int [n][n];
//Strings of length 1 are palindrome of lentgh 1
for (i = 0 ; i <n; i++)
L[i][i] = 1 ;
//Build the table. Note that the lower
//diagonal values of table are
//useless and not filled in the process.
//The values are filled in a manner similar
// to Matrix Chain Multiplication DP solution (See
//https://www.lsbin.org/matrix-chain-multiplication-dp-8/).
//cl is length of substring
for (cl= 2 ; cl<=n; cl++)
{
for (i= 0 ; i<n-cl+ 1 ; i++)
{
j = i+cl- 1 ;
if (seq.charAt(i) == seq.charAt(j) && cl == 2 )
L[i][j] = 2 ;
else if (seq.charAt(i) == seq.charAt(j))
L[i][j] = L[i+ 1 ][j- 1 ] + 2 ;
else
L[i][j] = max(L[i][j- 1 ], L[i+ 1 ][j]);
}
}
return L[ 0 ][n- 1 ];
}
/* Driver program to test above functions */
public static void main(String args[])
{
String seq = "lsbin" ;
int n = seq.length();
System.out.println( "The length of the lps is " + lps(seq));
}
}
/* This code is contributed by Rajat Mishra */
python
# A Dynamic Programming based Python
# program for LPS problem Returns the length
# of the longest palindromic subsequence in seq
def lps( str ):
n = len ( str )
# Create a table to store results of subproblems
L = [[ 0 for x in range (n)] for x in range (n)]
# Strings of length 1 are palindrome of length 1
for i in range (n):
L[i][i] = 1
# Build the table. Note that the lower
# diagonal values of table are
# useless and not filled in the process.
# The values are filled in a
# manner similar to Matrix Chain
# Multiplication DP solution (See
# https://www.lsbin.org/dynamic-programming-set-8-matrix-chain-multiplication/
# cl is length of substring
for cl in range ( 2 , n + 1 ):
for i in range (n - cl + 1 ):
j = i + cl - 1
if str [i] = = str [j] and cl = = 2 :
L[i][j] = 2
elif str [i] = = str [j]:
L[i][j] = L[i + 1 ][j - 1 ] + 2
else :
L[i][j] = max (L[i][j - 1 ], L[i + 1 ][j]);
return L[ 0 ][n - 1 ]
# Driver program to test above functions
seq = "GEEKS FOR GEEKS"
n = len (seq)
print ( "The length of the LPS is " + str (lps(seq)))
# This code is contributed by Bhavya Jain
C#
//A Dynamic Programming based C# Program
//for the Egg Dropping Puzzle
using System;
class GFG {
//A utility function to get max of
//two integers
static int max ( int x, int y)
{
return (x> y)? x : y;
}
//Returns the length of the longest
//palindromic subsequence in seq
static int lps( string seq)
{
int n = seq.Length;
int i, j, cl;
//Create a table to store results
//of subproblems
int [, ]L = new int [n, n];
//Strings of length 1 are
//palindrome of lentgh 1
for (i = 0; i <n; i++)
L[i, i] = 1;
//Build the table. Note that the
//lower diagonal values of table
//are useless and not filled in
//the process. The values are
//filled in a manner similar to
//Matrix Chain Multiplication DP
//solution (See
//https://www.lsbin.org/matrix-chain-multiplication-dp-8/
//cl is length of substring
for (cl = 2; cl <= n; cl++)
{
for (i = 0; i <n-cl+1; i++)
{
j = i + cl - 1;
if (seq[i] == seq[j] &&
cl == 2)
L[i, j] = 2;
else if (seq[i] == seq[j])
L[i, j] = L[i+1, j-1] + 2;
else
L[i, j] =
max(L[i, j-1], L[i+1, j]);
}
}
return L[0, n-1];
}
/* Driver program to test above
functions */
public static void Main()
{
string seq = "GEEKS FOR GEEKS" ;
int n = seq.Length;
Console.Write( "The length of the "
+ "lps is " + lps(seq));
}
}
//This code is contributed by nitin mittal.
PHP
<?php
//A Dynamic Programming based
//PHP program for LPS problem
//Returns the length of the
//longest palindromic
//subsequence in seq
//A utility function to get
//max of two integers
//function max( $x, $y)
//{ return ($x> $y)? $x : $y; }
//Returns the length of the
//longest palindromic
//subsequence in seq
function lps( $str )
{
$n = strlen ( $str );
$i ; $j ; $cl ;
//Create a table to store
//results of subproblems
$L [][] = array ( array ());
//Strings of length 1 are
//palindrome of lentgh 1
for ( $i = 0; $i <$n ; $i ++)
$L [ $i ][ $i ] = 1;
//Build the table. Note that
//the lower diagonal values
//of table are useless and
//not filled in the process.
//The values are filled in a
//manner similar to Matrix
//Chain Multiplication DP
//solution (See
//https://www.lsbin.org/matrix-chain-multiplication-dp-8/).
//cl is length of substring
for ( $cl = 2; $cl <= $n ; $cl ++)
{
for ( $i = 0; $i <$n - $cl + 1; $i ++)
{
$j = $i + $cl - 1;
if ( $str [ $i ] == $str [ $j ] &&
$cl == 2)
$L [ $i ][ $j ] = 2;
else if ( $str [ $i ] == $str [ $j ])
$L [ $i ][ $j ] = $L [ $i + 1][ $j - 1] + 2;
else
$L [ $i ][ $j ] = max( $L [ $i ][ $j - 1], $L [ $i + 1][ $j ]);
}
}
return $L [0][ $n - 1];
}
//Driver Code
$seq = 'GEEKS FOR GEEKS' ;
$n = strlen ( $seq );
echo "The length of the " .
"LPS is " , lps( $seq );
//This code is contributed
//by shiv_bhakt.
?>
输出如下:
The length of the LPS is 7
以上实现的时间复杂度为O(n ^ 2), 这比Naive Recursive实现的最坏情况下的时间复杂度要好得多。
打印最长回文序列
O(n)空间的最长回文序列
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
参考文献:
http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf