我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
当前回答
求最长递增子序列的O(NLog(N))方法 让我们维护一个数组，其中第i个元素是一个大小为i的子序列可以结束的最小的数字。
我故意避免进一步的细节，因为投票最多的答案已经解释了它，但这种技术最终导致使用set数据结构的整洁实现(至少在c++中)。
下面是c++中的实现(假设需要严格增加最长子序列的大小)
#include <bits/stdc++.h> // gcc supported header to include (almost) everything
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin >> n;
ll arr[n];
set<ll> S;
for(ll i=0; i<n; i++)
{
cin >> arr[i];
auto it = S.lower_bound(arr[i]);
if(it != S.end())
S.erase(it);
S.insert(arr[i]);
}
cout << S.size() << endl; // Size of the set is the required answer
return 0;
}
其他回答
Petar Minchev的解释帮助我理清了事情，但我很难解析所有内容，所以我做了一个带有过度描述性变量名和大量注释的Python实现。我做了一个简单的递归解，O(n²)解，和O(n log n)解。
我希望它能帮助理清算法!
递归解决方案
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²)动态规划解
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
这是另一个O(n²)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);
}
}
实际代码:http://ideone.com/sBiOQx
说到DP solution，我发现很奇怪的是没有人提到LIS可以简化为LCS。你所需要做的就是对原始序列的副本进行排序，删除所有重复的副本，然后对它们进行LCS。在伪代码中是:
def LIS(S):
T = sort(S)
T = removeDuplicates(T)
return LCS(S, T)
以及用Go语言编写的完整实现。如果你不需要重构解，你就不需要维护整个n^2 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]
}
求最长递增子序列的O(NLog(N))方法 让我们维护一个数组，其中第i个元素是一个大小为i的子序列可以结束的最小的数字。
我故意避免进一步的细节，因为投票最多的答案已经解释了它，但这种技术最终导致使用set数据结构的整洁实现(至少在c++中)。
下面是c++中的实现(假设需要严格增加最长子序列的大小)
#include <bits/stdc++.h> // gcc supported header to include (almost) everything
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin >> n;
ll arr[n];
set<ll> S;
for(ll i=0; i<n; i++)
{
cin >> arr[i];
auto it = S.lower_bound(arr[i]);
if(it != S.end())
S.erase(it);
S.insert(arr[i]);
}
cout << S.size() << endl; // Size of the set is the required answer
return 0;
}
这可以用动态规划在O(n²)中解决。
按顺序处理输入元素，并为每个元素维护一个元组列表。每个元组(A,B)，对于i将表示的元素，A =以i结尾的最长递增子序列的长度，B =以列表[i]结尾的最长递增子序列中列表[i]的前身的索引。
从元素1开始，元素1的元组列表为[(1,0)] 对于元素i，扫描列表0..i，找到元素list[k]，使得list[k] < list[i]，元素i的A值，Ai为Ak + 1, Bi为k。如果有多个这样的元素，将它们添加到元素i的元组列表中。
最后，找到所有最大值为A (LIS以element结尾的长度)的元素，并使用元组回溯以获得列表。
我已经在http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799上分享了相同的代码
