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

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

本文概述

给定一个序列, 找到其中最长回文子序列的长度。

最长回文序列

作为另一个示例, 如果给定序列为" 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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: