本文概述

• C++
• C
• Java
• Python3
• C#
• PHP
• C++
• Java
• python
• C#
• PHP

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

文章图片
作为另一个示例, 如果给定序列为" 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 approachclass 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 [] []来避免相同子问题的重新计算。
【算法设计（最长回文序列| DP-12）】动态编程解决方案
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

推荐阅读

• 

  叶酸片|几毛钱一片的小小叶酸片，却有大用途，3方面功效，本文为您说清
• 

  什么叫位似中心
• 

  ps安装的插件在拓展功能里找不到 ps安装插件后扩展功能里没有
• 

  梦见电梯是什么意思
• 

  221南通大学开学典礼 南通大学怎么样
• 

  虚胖的症状 一分钟分清你是否虚胖
• 

  天数|官宣！这一休假天数有变化，10月1日起施行
• 

  今日头条新闻手机版 今日头条新闻
• 

  有关狐狸的歇后语有哪些
• 

  菠菜鸡蛋汤怎么做好吃视频 菠菜鸡蛋汤怎么做
• 

  默默
• 

  三国志幻想大陆徐盛武将图鉴 三国志幻想大陆新武将徐盛怎么样
• 

  诗经抄写223〔小雅·蓼莪·后〕
• 

  价值观是什么意思举例说明 带你了解什么是人生最重要的五项价值观
• 

  硅胶手机壳和软胶有什么区别
• 

  海螺都能吃吗 山海螺能长期吃吗
• 

  如何恢复删掉好友的微信聊天记录 如何恢复删掉好友，如何恢复删掉好友的聊天记录
• 

  大暑一共多少天
• 

  如何降低车身重量 如何降低车身
• 

  公众号图片怎么弄成，公众号图片怎么弄成小图

• Infosys认证考试| InfyTQ
• Infosys认证考试| 2021-Fresher的InfyTQ
• Python中求两个数字的最大值的方法（）
• Codenation面试经验|习题集2（校园实习）
• 计算机网络| IP寻址问题7
• C编程面试常见问题S3
• C语言编程面试常见问题S2
• 高手解读Windows XP系统还原技巧运用攻略
• 如果忘记Windows XP系统登录密码的处理办法