# 算法设计：最长回文序列| DP-12

2021年4月16日19:33:46 发表评论 921 次浏览

## 本文概述

1)最佳子结构：

``````//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)重叠子问题

## 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``

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

## 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)空间的最长回文序列

http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf