给定一个序列，求其中最长回文子序列的长度。
null
另一个例子是，如果给定的序列是“BBABCBCAB”，那么输出应该是7，因为“babbbab”是其中最长的回文子序列。“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 1L(i, i) = 1 for all indexes i in given sequence// IF first and last characters are not sameIf (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 sameElse if (j == i + 1) L(i, j) = 2 // If there are more than two characters, and first and last // characters are sameElse 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[] = "GEEKSFORGEEKS" ; 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[] = "GEEKSFORGEEKS" ; 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 = "GEEKSFORGEEKS" ; 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 integers 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 = "GEEKSFORGEEKS" 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 = "GEEKSFORGEEKS" ; 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 = "GEEKSFORGEEKS" ; $n = strlen ( $seq ); echo "The length of the LPS is " . lps( $seq , 0, $n - 1); // This code is contributed by ita_c ?> |
Javascript
<script> // 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(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 program to test above function */ let seq = "GEEKSFORGEEKS" ; let n = seq.length; document.write( "The length of the LPS is " , lps(seq.split( "" ), 0, n - 1)); // This code is contributed by avanitrachhadiya2155 </script> |
输出
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问题有两个属性（参见 这 和 这 )一个动态规划问题。像其他典型的 动态规划问题 ，通过以自下而上的方式构造临时数组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 length 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.geeksforgeeks.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 length 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 // 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 = "GEEKSFORGEEKS" ; int n = seq.length(); System.out.println( "The length of the lps is " + lps(seq)); } } /* This code is contributed by Rajat Mishra */ |
Python3
# 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 # 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 length 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 // 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 length 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 // 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. ?> |
Javascript
<script> // A Dynamic Programming based Javascript // Program for the Egg Dropping Puzzle // 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(seq) { let n = seq.length; let i, j, cl; // Create a table to store results of subproblems let L = new Array(n); for (let x=0;x<n;x++) { L[x] = new Array(n); for (let y = 0; y < n; y++) L[x][y] = 0; } // Strings of length 1 are palindrome of length 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 // 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 */ let seq = "GEEKS FOR GEEKS" ; let n = seq.length; document.write( "The length of the lps is " + lps(seq)); // This code is contributed by rag2127 </script> |
输出
The length of the LPS is 7
上述实现的时间复杂度为O（n^2），这比朴素递归实现的最坏情况下的时间复杂度要好得多。
利用动态规划的记忆技术
这里使用的思想是反转给定的输入字符串，并检查字符串的长度 最长公共子序列 .这将是最长回文子序列的答案。
C++
// A Dynamic Programming based C++ program for LPS problem // Returns the length of the longest palindromic subsequence // in seq #include <bits/stdc++.h> using namespace std; int dp[1001][1001]; // Returns the length of the longest palindromic subsequence // in seq int lps(string& s1, string& s2, int n1, int n2) { if (n1 == 0 || n2 == 0) { return 0; } if (dp[n1][n2] != -1) { return dp[n1][n2]; } if (s1[n1 - 1] == s2[n2 - 1]) { return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1); } else { return dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1)); } } /* Driver program to test above functions */ int main() { string seq = "GEEKS FOR GEEKS" ; int n = seq.size(); dp[n][n]; memset (dp, -1, sizeof (dp)); string s2 = seq; reverse(s2.begin(), s2.end()); cout << "The length of the LPS is " << lps(s2, seq, n, n) << endl; return 0; } // This code is contributed by Arun Bang |
Javascript
<script> // A Dynamic Programming based JavaScript program for LPS problem // Returns the length of the longest palindromic subsequence // in seq let dp; // Returns the length of the longest palindromic subsequence // in seq function lps(s1, s2, n1, n2) { if (n1 == 0 || n2 == 0) { return 0; } if (dp[n1][n2] != -1) { return dp[n1][n2]; } if (s1[n1 - 1] == s2[n2 - 1]) { return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1); } else { return dp[n1][n2] = Math.max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1)); } } /* Driver program to test above functions */ let seq = "GEEKS FOR GEEKS" ; let n = seq.length; dp = new Array(1001); for (let i=0;i<1001;i++){ dp[i] = new Array(1001).fill(-1); } let s2 = seq; s2 = s2.split( '' ).reverse().join( '' ); document.write( "The length of the LPS is " + lps(s2, seq, n, n), "</br>" ); // This code is contributed by shinjanpatra </script> |
输出
The length of the LPS is 7
时间复杂性： O（n*n）
打印最长回文子序列 具有O（n）空间的最长回文子序列 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。 参考资料： http://users.eecs.northwestern.edu/~dda902/336/hw6溶胶。pdf
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
