LIS问题(Longest Increasing Subsequence Problem) 动态规划中经典的问题
简单来讲就是要找到一个序列中，所有递增子序列中长度最长的子序列的长度。子序列的取值不要求在原序列中连续。
动态规划
dp[i] 记录： 以arr[i]结尾的递增子序列的最大长度。
dp[i] 的更新：遍历 arr[0] 到 arr[i - 1] 中 小于 arr[i] 的数，并找到所有满足条件的arr[x] 中 dp[x] 最大的那个dp[n]，则dp[i] = dp[n] + 1
参考代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
int lis(int *arr, int length)
{
const int len = length;
int dp[len] = {0};
int tmpMax = 0;
for(int i = 0; i < length; ++i)
{
tmpMax = 0;
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j])
tmpMax = max(dp[j],tmpMax);
}
dp[i] = tmpMax + 1;
}
tmpMax = 0;
for(int i = 0; i < length; ++i)
{
if(dp[i] > tmpMax)
{
tmpMax = dp[i];
}
}
return tmpMax;
}
|
另一种递增，即必须严格递增，不能相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void lis(vector<int> &arr, vector<int> &dp)
{
const int len = arr.size();
for(int i = 0; i < len; ++i)
{
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
}
}
}
}
|
动态规划 + 二分
dp[i] 记录：当前最长的递增子序列的值
dp[i] 更新：把arr[i] 放入到 dp[i] 中，其放置方法为，从arr[0] 到 arr[len] 找到第一个大于等于arr[i]的位置pos，dp[pos] = arr[i]。并更新len = max(len,pos+1);
len增加（len < pos +1）的情况只有一种，便是在当前序列的末尾增加了一个数(pos = len)，反之如果只是在中间进行替换并不会改变len的大小。
注意到这里对 pos 的查找是对一个有序的序列的查找，可以使用二分查到达到log(n) 的复杂度。
参考代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
lisDich(int *arr, int length)
{
const int l = length;
int dp[l] = {0};
dp[0] = arr[0];
int len = 1;
for(int i = 1; i < length; ++i)
{
int pos = lower_bound(dp,dp+len,arr[i]) - dp;
dp[pos] = arr[i];
len = max(len,pos+1);
}
return len;
}
|
这里用到的函数函数lower_bound() 用于在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置
华为机试题 24题 合唱队
一种LIS的变种，通过正向与反向两次dp得到arr[i]左侧递增和右侧递减的长度，将两者相加得到一个满足条件的最大长度。
示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void lis(vector<int> &arr, vector<int> &dp)
{
const int len = arr.size();
for(int i = 0; i < len; ++i)
{
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
}
}
}
}
int calLis(vector<int> &arr)
{
const int size = arr.size();
vector<int> dpf(size,1);
vector<int> dpr(size,1);
vector<int> dp(size,1);
lis(arr,dpf);
reverse(arr.begin(),arr.end());
lis(arr,dpr);
reverse(dpr.begin(),dpr.end());
int max = 0;
for(int i = 0; i < size; ++i)
{
dp[i] = dpf[i] + dpr[i];
if(max < dp[i])
max = dp[i];
}
return max - 1;
}
int main(int argc, char *argv[])
{
int count = 0;
vector<int > arr;
while(cin>>count)
{
int tmp;
arr.clear();
while(count-- > 0)
{
cin>>tmp;
arr.push_back(tmp);
}
int len = arr.size() - calLis(arr);
cout<<len<<endl;
}
return 0;
}
|
