我们已经讨论过了 重叠子问题 和 最优子结构 财产。 现在，让我们讨论最长增长子序列（LIS）问题，作为一个可以使用动态规划解决的示例问题。
null
最长递增子序列（LIS）问题是求给定序列的最长子序列的长度，使子序列的所有元素按递增顺序排序。例如，{10,22,9,33,21,50,41,60,80}的LIS的长度是6，LIS的长度是{10,22,33,50,60,80}。
例如：
Input: arr[] = {3, 10, 2, 1, 20}Output: Length of LIS = 3The longest increasing subsequence is 3, 10, 20Input: arr[] = {3, 2}Output: Length of LIS = 1The longest increasing subsequences are {3} and {2}Input: arr[] = {50, 3, 10, 7, 40, 80}Output: Length of LIS = 4The longest increasing subsequence is {3, 7, 40, 80}
方法1 : 递归。 最佳子结构： 设arr[0..n-1]为输入数组，L（i）为以索引i结尾的LIS的长度，以使arr[i]为LIS的最后一个元素。
然后，L（i）可以递归地写为：
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; orL(i) = 1, if no such j exists.
为了找到给定数组的LIS，我们需要返回max（L（i）），其中0 形式上，以指数i结尾的最长递增子序列的长度将比以指数i之前结尾的所有最长递增子序列的最大长度大1，其中arr[j]
下面给出的递归树将使方法更清晰：
Input : arr[] = {3, 10, 2, 11}f(i): Denotes LIS of subarray ending at index 'i'(LIS(1)=1) f(4) {f(4) = 1 + max(f(1), f(2), f(3))} / | f(1) f(2) f(3) {f(3) = 1, f(2) and f(1) are > f(3)} | | f(1) f(2) f(1) {f(2) = 1 + max(f(1)} | f(1) {f(1) = 1}
下面是递归方法的实现：
C++
/* A Naive C++ recursive implementation of LIS problem */ #include <iostream> using namespace std; /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ int _lis( int arr[], int n, int * max_ref) { /* Base case */ if (n == 1) return 1; // 'max_ending_here' is length of LIS // ending with arr[n-1] int res, max_ending_here = 1; /* Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for ( int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall // max. And update the overall max if needed if (*max_ref < max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis( int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis(arr, n, &max); // returns max return max; } /* Driver program to test above function */ int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Length of lis is " << lis(arr, n); return 0; } // This code is contributed by shivanisinghss2110 |
C
/* A Naive C recursive implementation of LIS problem */ #include <stdio.h> #include <stdlib.h> /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ int _lis( int arr[], int n, int * max_ref) { /* Base case */ if (n == 1) return 1; // 'max_ending_here' is length of LIS // ending with arr[n-1] int res, max_ending_here = 1; /* Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for ( int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall // max. And update the overall max if needed if (*max_ref < max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis( int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis(arr, n, &max); // returns max return max; } /* Driver program to test above function */ int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Length of lis is %d" , lis(arr, n)); return 0; } |
JAVA
/* A Naive Java Program for LIS Implementation */ class LIS { static int max_ref; // stores the LIS /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ static int _lis( int arr[], int n) { // base case if (n == 1 ) return 1 ; // 'max_ending_here' is length of LIS ending with // arr[n-1] int res, max_ending_here = 1 ; /* Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for ( int i = 1 ; i < n; i++) { res = _lis(arr, i); if (arr[i - 1 ] < arr[n - 1 ] && res + 1 > max_ending_here) max_ending_here = res + 1 ; } // Compare max_ending_here with the overall max. And // update the overall max if needed if (max_ref < max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis( int arr[], int n) { // The max variable holds the result max_ref = 1 ; // The function _lis() stores its result in max _lis(arr, n); // returns max return max_ref; } // driver program to test above functions public static void main(String args[]) { int arr[] = { 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 }; int n = arr.length; System.out.println( "Length of lis is " + lis(arr, n) + "" ); } } /*This code is contributed by Rajat Mishra*/ |
Python3
# A naive Python implementation of LIS problem """ To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result """ # global variable to store the maximum global maximum def _lis(arr, n): # to allow the access of global variable global maximum # Base Case if n = = 1 : return 1 # maxEndingHere is the length of LIS ending with arr[n-1] maxEndingHere = 1 """Recursively get all LIS ending with arr[0], arr[1]..arr[n-2] IF arr[n-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it""" for i in range ( 1 , n): res = _lis(arr, i) if arr[i - 1 ] < arr[n - 1 ] and res + 1 > maxEndingHere: maxEndingHere = res + 1 # Compare maxEndingHere with overall maximum. And # update the overall maximum if needed maximum = max (maximum, maxEndingHere) return maxEndingHere def lis(arr): # to allow the access of global variable global maximum # length of arr n = len (arr) # maximum variable holds the result maximum = 1 # The function _lis() stores its result in maximum _lis(arr, n) return maximum # Driver program to test the above function arr = [ 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 ] n = len (arr) print ( "Length of lis is " , lis(arr)) # This code is contributed by NIKHIL KUMAR SINGH |
C#
using System; /* A Naive C# Program for LIS Implementation */ class LIS { static int max_ref; // stores the LIS /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ static int _lis( int [] arr, int n) { // base case if (n == 1) return 1; // 'max_ending_here' is length of LIS ending with // arr[n-1] int res, max_ending_here = 1; /* Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for ( int i = 1; i < n; i++) { res = _lis(arr, i); if (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall max. And // update the overall max if needed if (max_ref < max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis( int [] arr, int n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis(arr, n); // returns max return max_ref; } // driver program to test above functions public static void Main() { int [] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; Console.Write( "Length of lis is " + lis(arr, n) + "" ); } } |
Javascript
<script> /* A Naive javascript Program for LIS Implementation */ let max_ref; // stores the LIS /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ function _lis(arr,n) { // base case if (n == 1) return 1; // 'max_ending_here' is length of LIS ending with arr[n-1] let res, max_ending_here = 1; /* Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for (let i = 1; i < n; i++) { res = _lis(arr, i); if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall max. And // update the overall max if needed if (max_ref < max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() function lis(arr,n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis( arr, n); // returns max return max_ref; } // driver program to test above functions let arr=[10, 22, 9, 33, 21, 50, 41, 60 ] let n = arr.length; document.write( "Length of lis is " + lis(arr, n) + "<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
输出
Length of lis is 5
输出：
Length of lis is 5
复杂性分析：
- 时间复杂性： 这种递归方法的时间复杂度是指数的，因为存在重叠子问题的情况，如上面的递归树图所述。
- 辅助空间： O（1）。除了内部堆栈空间之外，没有用于存储值的外部空间。
方法2 : 动态规划。 我们可以看到，在上述递归解中，有许多子问题被反复求解。因此，该问题具有重叠子结构的性质，通过记忆或制表可以避免相同子问题的重新计算。
模拟方法将使事情变得清晰：
Input : arr[] = {3, 10, 2, 11}LIS[] = {1, 1, 1, 1} (initially)
迭代模拟：
- arr[2]>arr[1]{LIS[2]=max（LIS[2]，LIS[1]+1）=2}
- arr[3]
- arr[3]
- arr[4]>arr[1]{LIS[4]=max（LIS[4]，LIS[1]+1）=2}
- arr[4]>arr[2]{LIS[4]=max（LIS[4]，LIS[2]+1）=3}
- arr[4]>arr[3]{LIS[4]=max（LIS[4]，LIS[3]+1）=3}
- arr[3]
通过使用如下代码所示的表格，我们可以避免重新计算子问题：
以下是上述方法的实施情况：
C++
/* Dynamic Programming C++ implementation of LIS problem */ #include <bits/stdc++.h> using namespace std; /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ int lis( int arr[], int n) { int lis[n]; lis[0] = 1; /* Compute optimized LIS values in bottom up manner */ for ( int i = 1; i < n; i++) { lis[i] = 1; for ( int j = 0; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; } // Return maximum value in lis[] return *max_element(lis, lis + n); } /* Driver program to test above function */ int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Length of lis is %d" , lis(arr, n)); return 0; } |
JAVA
/* Dynamic Programming Java implementation of LIS problem */ class LIS { /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ static int lis( int arr[], int n) { int lis[] = new int [n]; int i, j, max = 0 ; /* Initialize LIS values for all indexes */ for (i = 0 ; i < n; i++) lis[i] = 1 ; /* Compute optimized LIS values in bottom up manner */ for (i = 1 ; i < n; i++) for (j = 0 ; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1 ) lis[i] = lis[j] + 1 ; /* Pick maximum of all LIS values */ for (i = 0 ; i < n; i++) if (max < lis[i]) max = lis[i]; return max; } public static void main(String args[]) { int arr[] = { 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 }; int n = arr.length; System.out.println( "Length of lis is " + lis(arr, n) + "" ); } } /*This code is contributed by Rajat Mishra*/ |
Python3
# Dynamic programming Python implementation # of LIS problem # lis returns length of the longest # increasing subsequence in arr of size n def lis(arr): n = len (arr) # Declare the list (array) for LIS and # initialize LIS values for all indexes lis = [ 1 ] * n # Compute optimized LIS values in bottom up manner for i in range ( 1 , n): for j in range ( 0 , i): if arr[i] > arr[j] and lis[i] < lis[j] + 1 : lis[i] = lis[j] + 1 # Initialize maximum to 0 to get # the maximum of all LIS maximum = 0 # Pick maximum of all LIS values for i in range (n): maximum = max (maximum, lis[i]) return maximum # end of lis function # Driver program to test above function arr = [ 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 ] print ( "Length of lis is" , lis(arr)) # This code is contributed by Nikhil Kumar Singh |
C#
/* Dynamic Programming C# implementation of LIS problem */ using System; class LIS { /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ static int lis( int [] arr, int n) { int [] lis = new int [n]; int i, j, max = 0; /* Initialize LIS values for all indexes */ for (i = 0; i < n; i++) lis[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Pick maximum of all LIS values */ for (i = 0; i < n; i++) if (max < lis[i]) max = lis[i]; return max; } public static void Main() { int [] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; Console.WriteLine( "Length of lis is " + lis(arr, n) + "" ); } // This code is contributed by Ryuga } |
Javascript
<script> // Dynamic Programming Javascript implementation // of LIS problem // lis() returns the length of the longest // increasing subsequence in arr[] of size n function lis(arr, n) { let lis = Array(n).fill(0); let i, j, max = 0; // Initialize LIS values for all indexes for (i = 0; i < n; i++) lis[i] = 1; // Compute optimized LIS values in // bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; // Pick maximum of all LIS values for (i = 0; i < n; i++) if (max < lis[i]) max = lis[i]; return max; } // Driver code let arr = [ 10, 22, 9, 33, 21, 50, 41, 60 ]; let n = arr.length; document.write( "Length of lis is " + lis(arr, n) + "" ); // This code is contributed by avijitmondal1998 </script> |
输出
Length of lis is 5
复杂性分析：
- 时间复杂性： O（n） 2. ). 因为使用了嵌套循环。
- 辅助空间： O（n）。 使用任何数组在每个索引处存储LIS值。
注： 上述动态规划（DP）解决方案的时间复杂度为O（n^2），LIS问题有一个O（n logn）解决方案。我们在这里没有讨论O（N logn）解，因为这篇文章的目的是用一个简单的例子来解释动态规划。关于O（N logn）解决方案，请参见下面的帖子。 最长递增子序列大小（N logn）
方法3： 动态规划
如果我们仔细观察这个问题，我们就可以把这个问题转化为最长的公共子序列问题。首先，我们将创建另一个由原始数组的唯一元素组成的数组，并对其进行排序。现在，数组中最长的递增子序列必须作为排序数组中的子序列出现。这就是为什么我们的问题现在归结为寻找两个数组之间的公共子序列。
Eg. arr =[50,3,10,7,40,80] // Sorted array arr1 = [3,7,10,40,50,80] // LIS is longest common subsequence between the two arrays ans = 4 The longest increasing subsequence is {3, 7, 40, 80}
C++
// Dynamic Programming Approach of Finding LIS by reducing // the problem to longest common Subsequence #include <bits/stdc++.h> using namespace std; /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ int lis( int arr[], int n) { vector< int > b; set< int > s; // setting iterator for set set< int >::iterator it; // storing unique elements for ( int i = 0; i < n; i++) { s.insert(arr[i]); } // creating sorted vector for (it = s.begin(); it != s.end(); it++) { b.push_back(*it); } int m = b.size(), i, j; int dp[m + 1][n + 1]; // storing -1 in dp multidimensional array for (i = 0; i < m + 1; i++) { for (j = 0; j < n + 1; j++) { dp[i][j] = -1; } } // Finding Longest common Subsequence of the two // arrays for (i = 0; i < m + 1; i++) { for (j = 0; j < n + 1; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (arr[j - 1] == b[i - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } /* Driver program to test above function */ int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Length of lis is %d" , lis(arr, n)); } /* This code is contributed by Arun Bang */ |
JAVA
import static java.lang.Math.max; import java.util.SortedSet; import java.util.TreeSet; // Dynamic Programming Approach of Finding LIS by reducing // the problem to longest common Subsequence public class Main { /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ static int lis( int arr[], int n) { SortedSet<Integer> hs = new TreeSet<Integer>(); // Storing and Sorting unique elements. for ( int i = 0 ; i < n; i++) hs.add(arr[i]); int lis[] = new int [hs.size()]; int k = 0 ; // Storing all the unique values in a sorted manner. for ( int val : hs) { lis[k] = val; k++; } int m = k, i, j; int dp[][] = new int [m + 1 ][n + 1 ]; // Storing -1 in dp multidimensional array. for (i = 0 ; i < m + 1 ; i++) { for (j = 0 ; j < n + 1 ; j++) { dp[i][j] = - 1 ; } } // Finding the Longest Common Subsequence of the two // arrays for (i = 0 ; i < m + 1 ; i++) { for (j = 0 ; j < n + 1 ; j++) { if (i == 0 || j == 0 ) { dp[i][j] = 0 ; } else if (arr[j - 1 ] == lis[i - 1 ]) { dp[i][j] = 1 + dp[i - 1 ][j - 1 ]; } else { dp[i][j] = max(dp[i - 1 ][j], dp[i][j - 1 ]); } } } return dp[m][n]; } // Driver Program for the above test function. public static void main(String[] args) { int arr[] = { 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 }; int n = arr.length; System.out.println( "Length of lis is " + lis(arr, n) + "" ); } } // This Code is Contributed by Omkar Subhash Ghongade |
Python3
# Dynamic Programming Approach of Finding LIS by reducing the problem to longest common Subsequence def lis(a): n = len (a) # Creating the sorted list b = sorted ( list ( set (a))) m = len (b) # Creating dp table for storing the answers of sub problems dp = [[ - 1 for i in range (m + 1 )] for j in range (n + 1 )] # Finding Longest common Subsequence of the two arrays for i in range (n + 1 ): for j in range (m + 1 ): if i = = 0 or j = = 0 : dp[i][j] = 0 elif a[i - 1 ] = = b[j - 1 ]: dp[i][j] = 1 + dp[i - 1 ][j - 1 ] else : dp[i][j] = max (dp[i - 1 ][j], dp[i][j - 1 ]) return dp[ - 1 ][ - 1 ] # Driver program to test above function arr = [ 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 ] print ( "Length of lis is " , lis(arr)) # This code is Contributed by Dheeraj Khatri |
输出
Length of lis is 5
复杂性分析 ：O（n*n）
因为使用了嵌套循环
空间复杂性 ：O（n*n）
因为矩阵用于存储值。
https://www.youtube.com/watch?v=Ns4LCeeOFS4
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
