我有一组整数。我想使用动态规划找到该集合的最长递增子序列。
如何使用动态规划确定最长递增子序列？
235
- Tony
2
12关于 DP 解法，我发现很惊讶没有人提到一个事实，即LIS 可以简化为 LCS。 - Salvador Dali
非常好地解释了[LIS]（https://leetcode.com/problems/longest-increasing-subsequence/discuss/1326308/C%2B%2BPython-DP-Binary-Search-BIT-Solutions-Picture-explain-O(NlogN)）。 - Sumit
21个回答
438
好的，首先我将描述最简单的解决方案，它的时间复杂度为O(N^2)，其中N是集合的大小。还有一种时间复杂度为O(N log N)的解决方案，我也会进行描述。在这里查看高效算法部分。
我假设数组的索引从0到N-1。因此，我们定义 DP[i] 为以索引 i 结尾的最长增长子序列（LIS）的长度。为了计算 DP [i] ，我们查看所有索引 j<i 并检查 DP [j] +1 > DP [i] 和 array [j] < array [i] 是否都成立（我们希望它递增）。如果成立，则可以更新当前最优值为 DP [i] 。要找到数组的全局最优解，您可以从 DP [0 ... N-1] 中取最大值。
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
我使用数组prev，以便稍后不仅能找到实际序列的长度，而且能找到实际序列。只需从循环中的bestEnd递归向后移动，使用prev[bestEnd]。值-1是停止的标志。
现在来看更高效的O(N log N)解决方案：
将S[pos]定义为以整数pos结尾的最小增长序列。现在遍历输入集合中的每个整数X并执行以下操作：
- 如果
X大于S中的最后一个元素，则将X附加到S的末尾。这基本上意味着我们已经找到了一个新的最大LIS。 - 否则，在
S中找到>=X的最小元素，并将其更改为X。由于S随时都是有序的，可以使用二分查找在log(N)内找到该元素。
总运行时间 - 每个整数N和一次二分查找 - N * log(N) = O(N log N)
现在来看一个真实的例子：
整数集合：2 6 3 4 1 2 9 5 8
步骤：
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
因此，LIS的长度为 5（即S的大小）。
为了重构实际的 LIS，我们将再次使用一个父数组。令parent[i]是索引为 i 的元素在以索引为 i 结尾的 LIS 中的前一个元素。
为了简化问题，我们可以在数组S中保存元素的位置而不是它们的实际整数值。我们不会保留 {1, 2, 4, 5, 8}，而是保留 {4, 5, 3, 7, 8}。
也就是说，input[4] = 1，input[5] = 2，input[3] = 4，input[7] = 5，input[8] = 8。
如果我们正确地更新了父数组，那么实际的LIS即为：
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
现在重要的是 - 我们如何更新父数组呢？有两种选择：
如果
X>S中的最后一个元素，则parent[indexX] = indexLastElement。这意味着最新元素的父元素是最后一个元素。我们只需将X添加到S的末尾即可。否则找到
S中大于或等于X的最小元素的索引，将其更改为X。在这种情况下，parent[indexX] = S[index - 1]。
- Petar Minchev
40
13但是这里的答案应该是
[1,2,5,8]，因为在数组中 4 在 1 的前面，怎么可能让 LIS 变成 [1,2,4,5,8] 呢？ - SexyBeast24答案是
[2,3,4,5,8]。请仔细阅读 - S 数组 并不代表 一个实际的序列。让 S[pos] 定义为以长度 pos 结尾的递增序列中的最小整数。 - Petar Minchev8我很少见到如此清晰的解释。它不仅易于理解，因为疑惑已经在解释中解决，而且还解决了任何可能出现的实施问题。太棒了。 - Boyang
17这可能是我看过的最好的解释：http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ - eb80
4@PetarMinchev的解释很棒。比geeksforgeeks.org和维基百科都要好得多。非常感谢您清晰简明地解释了这个问题。 - Ali
显示剩余35条评论
64
Petar Minchev的解释帮助我理清了思路，但对于我来说，很难解析出所有的内容，因此我使用了过度描述的变量名和大量注释进行了一个Python实现。我做了一个朴素递归解法，O(n^2)解法和O(nlogn)解法。
我希望这有助于澄清算法！
递归解法
def recursive_solution(remaining_sequence, bigger_than=None):
"""Finds the longest increasing subsequence of remaining_sequence that is
bigger than bigger_than and returns it. This solution is O(2^n)."""
# Base case: nothing is remaining.
if len(remaining_sequence) == 0:
return remaining_sequence
# Recursive case 1: exclude the current element and process the remaining.
best_sequence = recursive_solution(remaining_sequence[1:], bigger_than)
# Recursive case 2: include the current element if it's big enough.
first = remaining_sequence[0]
if (first > bigger_than) or (bigger_than is None):
sequence_with = [first] + recursive_solution(remaining_sequence[1:], first)
# Choose whichever of case 1 and case 2 were longer.
if len(sequence_with) >= len(best_sequence):
best_sequence = sequence_with
return best_sequence
O(n^2)动态规划解决方案
def dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming. This solution is O(n^2)."""
longest_subsequence_ending_with = []
backreference_for_subsequence_ending_with = []
current_best_end = 0
for curr_elem in range(len(sequence)):
# It's always possible to have a subsequence of length 1.
longest_subsequence_ending_with.append(1)
# If a subsequence is length 1, it doesn't have a backreference.
backreference_for_subsequence_ending_with.append(None)
for prev_elem in range(curr_elem):
subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1)
# If the prev_elem is smaller than the current elem (so it's increasing)
# And if the longest subsequence from prev_elem would yield a better
# subsequence for curr_elem.
if ((sequence[prev_elem] < sequence[curr_elem]) and
(subsequence_length_through_prev >
longest_subsequence_ending_with[curr_elem])):
# Set the candidate best subsequence at curr_elem to go through prev.
longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev)
backreference_for_subsequence_ending_with[curr_elem] = prev_elem
# If the new end is the best, update the best.
if (longest_subsequence_ending_with[curr_elem] >
longest_subsequence_ending_with[current_best_end]):
current_best_end = curr_elem
# Output the overall best by following the backreferences.
best_subsequence = []
current_backreference = current_best_end
while current_backreference is not None:
best_subsequence.append(sequence[current_backreference])
current_backreference = (backreference_for_subsequence_ending_with[current_backreference])
best_subsequence.reverse()
return best_subsequence
O(n log n) 时间复杂度的动态规划解法
def find_smallest_elem_as_big_as(sequence, subsequence, elem):
"""Returns the index of the smallest element in subsequence as big as
sequence[elem]. sequence[elem] must not be larger than every element in
subsequence. The elements in subsequence are indices in sequence. Uses
binary search."""
low = 0
high = len(subsequence) - 1
while high > low:
mid = (high + low) / 2
# If the current element is not as big as elem, throw out the low half of
# sequence.
if sequence[subsequence[mid]] < sequence[elem]:
low = mid + 1
# If the current element is as big as elem, throw out everything bigger, but
# keep the current element.
else:
high = mid
return high
def optimized_dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming and binary search (per
http://en.wikipedia.org/wiki/Longest_increasing_subsequence). This solution
is O(n log n)."""
# Both of these lists hold the indices of elements in sequence and not the
# elements themselves.
# This list will always be sorted.
smallest_end_to_subsequence_of_length = []
# This array goes along with sequence (not
# smallest_end_to_subsequence_of_length). Following the corresponding element
# in this array repeatedly will generate the desired subsequence.
parent = [None for _ in sequence]
for elem in range(len(sequence)):
# We're iterating through sequence in order, so if elem is bigger than the
# end of longest current subsequence, we have a new longest increasing
# subsequence.
if (len(smallest_end_to_subsequence_of_length) == 0 or
sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]):
# If we are adding the first element, it has no parent. Otherwise, we
# need to update the parent to be the previous biggest element.
if len(smallest_end_to_subsequence_of_length) > 0:
parent[elem] = smallest_end_to_subsequence_of_length[-1]
smallest_end_to_subsequence_of_length.append(elem)
else:
# If we can't make a longer subsequence, we might be able to make a
# subsequence of equal size to one of our earlier subsequences with a
# smaller ending number (which makes it easier to find a later number that
# is increasing).
# Thus, we look for the smallest element in
# smallest_end_to_subsequence_of_length that is at least as big as elem
# and replace it with elem.
# This preserves correctness because if there is a subsequence of length n
# that ends with a number smaller than elem, we could add elem on to the
# end of that subsequence to get a subsequence of length n+1.
location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
smallest_end_to_subsequence_of_length[location_to_replace] = elem
# If we're replacing the first element, we don't need to update its parent
# because a subsequence of length 1 has no parent. Otherwise, its parent
# is the subsequence one shorter, which we just added onto.
if location_to_replace != 0:
parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1])
# Generate the longest increasing subsequence by backtracking through parent.
curr_parent = smallest_end_to_subsequence_of_length[-1]
longest_increasing_subsequence = []
while curr_parent is not None:
longest_increasing_subsequence.append(sequence[curr_parent])
curr_parent = parent[curr_parent]
longest_increasing_subsequence.reverse()
return longest_increasing_subsequence
- Sam King
12
24虽然我感谢您的努力，但当我盯着那些伪代码看时，我的眼睛会疼。 - mostruash
103mostruash -- 我不确定你的意思。我的回答没有伪代码，而是用Python编写的。 - Sam King
12他很可能指的是你的变量和函数命名规范，这也让我感到不舒服。 - Adilli Adil
24如果您指的是我的命名规则，我大多遵循Google Python风格指南。如果您主张使用短变量名，我更喜欢使用描述性的变量名，因为它们可以使代码更易于理解和维护。 - Sam King
11对于实际实现而言，使用
bisect可能更加合理。而在演示算法的工作原理和性能特征时，我试图尽可能保持简单原始。 - Sam King显示剩余7条评论
29
谈到DP解决方案，我发现令人惊讶的是没有人提到LIS可以被简化为LCS问题。你只需要对原序列进行排序，删除所有重复项，然后对它们进行LCS。伪代码如下：
def LIS(S):
T = sort(S)
T = removeDuplicates(T)
return LCS(S, T)
这是用Go语言编写的完整实现。如果您不需要重构解决方案，则不需要维护整个n² DP矩阵。
func lcs(arr1 []int) int {
arr2 := make([]int, len(arr1))
for i, v := range arr1 {
arr2[i] = v
}
sort.Ints(arr1)
arr3 := []int{}
prev := arr1[0] - 1
for _, v := range arr1 {
if v != prev {
prev = v
arr3 = append(arr3, v)
}
}
n1, n2 := len(arr1), len(arr3)
M := make([][]int, n2 + 1)
e := make([]int, (n1 + 1) * (n2 + 1))
for i := range M {
M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)]
}
for i := 1; i <= n2; i++ {
for j := 1; j <= n1; j++ {
if arr2[j - 1] == arr3[i - 1] {
M[i][j] = M[i - 1][j - 1] + 1
} else if M[i - 1][j] > M[i][j - 1] {
M[i][j] = M[i - 1][j]
} else {
M[i][j] = M[i][j - 1]
}
}
}
return M[n2][n1]
}
- Salvador Dali
1
@max 是的，它在使用LCS和n^2矩阵的答案中有所体现。 - Salvador Dali
10
以下的C++实现中还包括一些构建实际
prev 数组的最长递增子序列代码。std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
int best_end = 0;
int sz = s.size();
if (!sz)
return std::vector<int>();
std::vector<int> prev(sz,-1);
std::vector<int> memo(sz, 0);
int max_length = std::numeric_limits<int>::min();
memo[0] = 1;
for ( auto i = 1; i < sz; ++i)
{
for ( auto j = 0; j < i; ++j)
{
if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
{
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if ( memo[i] > max_length )
{
best_end = i;
max_length = memo[i];
}
}
// Code that builds the longest increasing subsequence using "prev"
std::vector<int> results;
results.reserve(sz);
std::stack<int> stk;
int current = best_end;
while (current != -1)
{
stk.push(s[current]);
current = prev[current];
}
while (!stk.empty())
{
results.push_back(stk.top());
stk.pop();
}
return results;
}
不使用堆栈，只需反转向量即可实现
#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
auto sz = v.size();
if(!sz)
return v;
std::vector<int> memo(sz, 0);
std::vector<int> prev(sz, -1);
memo[0] = 1;
int best_end = 0;
int max_length = std::numeric_limits<int>::min();
for (auto i = 1; i < sz; ++i) {
for ( auto j = 0; j < i ; ++j) {
if (s[j] < s[i] && memo[i] < memo[j] + 1) {
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if(memo[i] > max_length) {
best_end = i;
max_length = memo[i];
}
}
// create results
std::vector<int> results;
results.reserve(v.size());
auto current = best_end;
while (current != -1) {
results.push_back(s[current]);
current = prev[current];
}
std::reverse(results.begin(), results.end());
return results;
}
- bjackfly
4
以下是从动态规划角度评估问题的三个步骤：
- 递归定义：maxLength(i) == 1 + maxLength(j)，其中0 < j < i且array[i] > array[j]
- 递归参数边界：可能会有0到i-1个子序列作为参数
- 评估顺序：由于这是一个递增的子序列，所以必须从0到n进行评估
- [0] 我们将得到子序列{0}作为基本情况
- [1] 我们有1个新的子序列{0,8}
- [2] 尝试通过将索引2处的元素添加到现有子序列来评估两个新序列{0,8,2}和{0,2} - 只有一个是有效的，因此将第三个可能的序列{0,2} 添加到参数列表中 ...
#include <iostream>
#include <vector>
int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) {
if(index == 0) {
sub.push_back(std::vector<int>{sequence[0]});
return 1;
}
size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub);
std::vector<std::vector<int>> tmpSubSeq;
for(std::vector<int> &subSeq : sub) {
if(subSeq[subSeq.size() - 1] < sequence[index]) {
std::vector<int> newSeq(subSeq);
newSeq.push_back(sequence[index]);
longestSubSeq = std::max(longestSubSeq, newSeq.size());
tmpSubSeq.push_back(newSeq);
}
}
std::copy(tmpSubSeq.begin(), tmpSubSeq.end(),
std::back_insert_iterator<std::vector<std::vector<int>>>(sub));
return longestSubSeq;
}
int getLongestIncSub(const std::vector<int> &sequence) {
std::vector<std::vector<int>> sub;
return getLongestIncSub(sequence, sequence.size() - 1, sub);
}
int main()
{
std::vector<int> seq{0, 8, 2, 3, 7, 9};
std::cout << getLongestIncSub(seq);
return 0;
}
- Iuri Covalisin
1
我认为递归定义应该是 maxLength(i) = 1 + max(maxLength(j))，其中 0 < j < i 且 array[i] > array[j]，而不是没有 max()。 - Slothworks
1
这是另一种O(n^2)的JAVA实现。没有使用递归/记忆化来生成实际的子序列。只需使用一个字符串数组来存储每个阶段的实际LIS和一个数组来存储每个元素的LIS长度。非常简单易懂。看一下：
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
* Created by Shreyans on 4/16/2015
*/
class LNG_INC_SUB//Longest Increasing Subsequence
{
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter Numbers Separated by Spaces to find their LIS\n");
String[] s1=br.readLine().split(" ");
int n=s1.length;
int[] a=new int[n];//Array actual of Numbers
String []ls=new String[n];// Array of Strings to maintain LIS for every element
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(s1[i]);
}
int[]dp=new int[n];//Storing length of max subseq.
int max=dp[0]=1;//Defaults
String seq=ls[0]=s1[0];//Defaults
for(int i=1;i<n;i++)
{
dp[i]=1;
String x="";
for(int j=i-1;j>=0;j--)
{
//First check if number at index j is less than num at i.
// Second the length of that DP should be greater than dp[i]
// -1 since dp of previous could also be one. So we compare the dp[i] as empty initially
if(a[j]<a[i]&&dp[j]>dp[i]-1)
{
dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j]
x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on
}
}
x+=(" "+a[i]);
ls[i]=x;
if(dp[i]>max)
{
max=dp[i];
seq=ls[i];
}
}
System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq);
}
}
- gabbar0x
1
这是一个Java O(nlogn)的实现。
import java.util.Scanner;
public class LongestIncreasingSeq {
private static int binarySearch(int table[],int a,int len){
int end = len-1;
int beg = 0;
int mid = 0;
int result = -1;
while(beg <= end){
mid = (end + beg) / 2;
if(table[mid] < a){
beg=mid+1;
result = mid;
}else if(table[mid] == a){
return len-1;
}else{
end = mid-1;
}
}
return result;
}
public static void main(String[] args) {
// int[] t = {1, 2, 5,9,16};
// System.out.println(binarySearch(t , 9, 5));
Scanner in = new Scanner(System.in);
int size = in.nextInt();//4;
int A[] = new int[size];
int table[] = new int[A.length];
int k = 0;
while(k<size){
A[k++] = in.nextInt();
if(k<size-1)
in.nextLine();
}
table[0] = A[0];
int len = 1;
for (int i = 1; i < A.length; i++) {
if(table[0] > A[i]){
table[0] = A[i];
}else if(table[len-1]<A[i]){
table[len++]=A[i];
}else{
table[binarySearch(table, A[i],len)+1] = A[i];
}
}
System.out.println(len);
}
}
//TreeSet可以使用
- fatih tekin
1
这是一个Scala实现的O(n^2)算法：
object Solve {
def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = {
xs.foldLeft(List[(Int, List[T])]()) {
(sofar, x) =>
if (sofar.isEmpty) List((1, List(x)))
else {
val resIfEndsAtCurr = (sofar, xs).zipped map {
(tp, y) =>
val len = tp._1
val seq = tp._2
if (ord.lteq(y, x)) {
(len + 1, x :: seq) // reversely recorded to avoid O(n)
} else {
(1, List(x))
}
}
sofar :+ resIfEndsAtCurr.maxBy(_._1)
}
}.maxBy(_._1)._2.reverse
}
def main(args: Array[String]) = {
println(longestIncrSubseq(List(
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)))
}
}
- lcn
0
这是一个O(n^2)的Java实现。我没有使用二分查找来找到S中大于或等于X的最小元素，而是使用了for循环。使用二分查找会使复杂度达到O(n logn)。
public static void olis(int[] seq){
int[] memo = new int[seq.length];
memo[0] = seq[0];
int pos = 0;
for (int i=1; i<seq.length; i++){
int x = seq[i];
if (memo[pos] < x){
pos++;
memo[pos] = x;
} else {
for(int j=0; j<=pos; j++){
if (memo[j] >= x){
memo[j] = x;
break;
}
}
}
//just to print every step
System.out.println(Arrays.toString(memo));
}
//the final array with the LIS
System.out.println(Arrays.toString(memo));
System.out.println("The length of lis is " + (pos + 1));
}
- Shashank Agarwal
0
查看使用Java编写的代码，获取数组元素中最长递增子序列
/**
** Java Program to implement Longest Increasing Subsequence Algorithm
**/
import java.util.Scanner;
/** Class LongestIncreasingSubsequence **/
class LongestIncreasingSubsequence
{
/** function lis **/
public int[] lis(int[] X)
{
int n = X.length - 1;
int[] M = new int[n + 1];
int[] P = new int[n + 1];
int L = 0;
for (int i = 1; i < n + 1; i++)
{
int j = 0;
/** Linear search applied here. Binary Search can be applied too.
binary search for the largest positive j <= L such that
X[M[j]] < X[i] (or set j = 0 if no such value exists) **/
for (int pos = L ; pos >= 1; pos--)
{
if (X[M[pos]] < X[i])
{
j = pos;
break;
}
}
P[i] = M[j];
if (j == L || X[i] < X[M[j + 1]])
{
M[j + 1] = i;
L = Math.max(L,j + 1);
}
}
/** backtrack **/
int[] result = new int[L];
int pos = M[L];
for (int i = L - 1; i >= 0; i--)
{
result[i] = X[pos];
pos = P[pos];
}
return result;
}
/** Main Function **/
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Longest Increasing Subsequence Algorithm Test\n");
System.out.println("Enter number of elements");
int n = scan.nextInt();
int[] arr = new int[n + 1];
System.out.println("\nEnter "+ n +" elements");
for (int i = 1; i <= n; i++)
arr[i] = scan.nextInt();
LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence();
int[] result = obj.lis(arr);
/** print result **/
System.out.print("\nLongest Increasing Subsequence : ");
for (int i = 0; i < result.length; i++)
System.out.print(result[i] +" ");
System.out.println();
}
}
- jayant singh
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接