参考:https://oi-wiki.org/dp/basic/

最长公共子序列(LCS)

LCS即求2个序列最长的公共子序列(可以不连续).

给定2个序列S1和S2S_1和S_2,长度分别为m和nm和n.记S1S_1的前ii个字符和S2S_2的前jj个字符的最长公共子序列长度为LCS(i,j)LCS(i,j),则最终结果S1S_1和S2S_2的最长公共子序列长度为LCS(m,n)LCS(m,n)

状态转移方程为:

LCS(i,j)={0, (i=0 or j=0)LCS(i−1,j−1)+1, (S1[i]=S2[j])max(LCS(i−1,j),LCS(i,j−1)), (S1[i]≠S2[j])LCS(i,j)= \begin{cases} 0,\ (i=0\ or\ j=0)\\ LCS(i-1,j-1)+1,\ (S_1[i]=S_2[j])\\ max(LCS(i-1,j),LCS(i,j-1)),\ (S_1[i]\ne S_2[j]) \end{cases}

常规方法(二维DP)

使用二维数组f[m+1][n+1]来对LCS()进行迭代即可编写代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>

#define MAXN 100
#define MAXM 1000
int a[MAXN], b[MAXM], f[MAXN][MAXM];
int n, m;
int dp() {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (a[i] == b[j])
        f[i][j] = f[i - 1][j - 1] + 1;
      else
        f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
  return f[n][m];
}

易知该方法的时间复杂度为O(mn)O(mn),空间复杂度为O(mn)O(mn)

空间优化(一维DP)

根据状态转移方程容易发现,当前行的各状态只与上一行的各状态有关,因此可以将n*m的dp数组优化为只有一行的滚动数组.

当外层循环到第i层时,dp数组代表当循环到S1[i]S_1[i]字符时的状态数组.更新dp[j],即为更新原二维dp中的dp[i][j].此时的dp[j]保存的"应该"是dp[i-1][j],而dp[j-1]中保存的是dp[i][j-1],现在的问题是如何获取dp[i-1][j-1].

可以使用一个old变量,来保存当前循环时,更新前的dp[j],即为"当前"的dp[i-1][j],那么当循环到下一次时(即第j+1个字符),old的值就是dp[i-1][j-1](即该值已成为过去式).

另外,尽管使用一个old来存储dp[i-1][j-1],但是在循环中难免要获取更新的值,使用一个temp变量来临时存储.

由此便可将O(mn)O(mn)的空间复杂度优化为O(m)O(m),不过代码较难理解,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>

#define MAXN 100
#define MAXM 1000
int a[MAXN], b[MAXM], f[MAXM];
int n, m;

int dp() {
	int temp = 0, old = 0;
	for (int i = 1; i <= n; ++i) {
		old = f[0]; // 设置初始的old=f[i-1][0]
		for (int j = 1; j <= m; ++j) {
			temp = f[j]; // 当前,更新前的f[i-1][j]
			if (a[i] == b[j]) {
				f[j] = old + 1;
			} else {
				f[j] = std::max(f[j - 1], f[j]);
			}
			old = temp; // 更新新的old值
		}
	}
	return f[m];
}

最长上升子序列(LIS)

法一:O(n2)O(n^2)的DP

给定字符串S,求其LIS.

定义f[i](i∈[1,n])f[i](i \in [1,n])为串S的以字符S[i]S[i]结尾的最长上升子序列的长度.

最终答案LIS(S)=max{f[1],f[2],...,f[n]}LIS(S)=max\{f[1],f[2],...,f[n]\}

有状态方程如下:

初始条件: f[i]=1(1≤i≤n)f[i]=max{f[j]+1,f[i]} (1≤j<i,S[j]<S[i])初始条件:\ f[i]=1 (1 \le i \le n)\\ f[i]=max\{ f[j]+1,f[i] \}\ (1 \le j \lt i,S[j] \lt S[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
#include <iostream>
#define MAXN 5001
using namespace std;

int dp(int s[], int f[], int n) {
	int ans = 0;
	for (int i = 0;i < n;++i) {
		f[i] = 1;
		for (int j = 0;j < i;++j) {
			if (s[j] < s[i]) {
				f[i] = max(f[i], f[j] + 1);
			}
		}
		ans = max(ans, f[i]);
	}
	return ans;
}

int main() {
	int s[MAXN];
	int f[MAXN];
	int n;
	cin >> n;
	for (int i = 0;i < n;++i)
		cin >> s[i];
	int ans = dp(s, f, n); // dp
	cout << ans;
	return 0;
}

法二:O(nlogn)O(nlogn)的贪心+二分查找

使用一个low[]数组.其中low[i]low[i]代表长度为ii的LIS序列结尾元素的最小值.

我们对整个SS进行遍历,每次访问S[i]S[i],检查其和low[ans]low[ans]的大小关系,如果S[i]>low[ans]S[i] \gt low[ans],则直接将其连接在low[ans]后面;否则,搜索low[]中第一个≥s[i]\ge s[i]的元素,并对其进行替换.

最终ans即为所求的LIS长度.

显然low[]数组是严格不下降的,因此对于low[]的搜索可以使用二分查找来优化.这样便可以将时间复杂度优化为O(nlogn)O(nlogn).

需要注意的是,now[]数组中存储的并不一定是正确的最长上升子序列,而是为后续的迭代做好准备的序列.

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
65
66
67
68
69
70
71
72
73
#include <iostream>
#define MAXN 5001
using namespace std;

int dp(int s[], int f[], int n) {
    // 朴素DP
	int ans = 0;
	for (int i = 0;i < n;++i) {
		f[i] = 1;
		for (int j = 0;j < i;++j) {
			if (s[j] < s[i]) {
				f[i] = max(f[i], f[j] + 1);
			}
		}
		ans = max(ans, f[i]);
	}
	return ans;
}

int bsearch(int *arr, int n,int key) {
    int l = 0, r = n - 1;
    while (l <= r) {
        //int mid = l + ((r-l)>>1); // 避免溢出
        int mid = l + r >> 1;
        if (arr[mid] >= key)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return l;
}

int bsearch2(int arr[], int n, int key) {
	int l = 0, r = n - 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (arr[mid] >= key)
			r = mid;
		else
			l = mid + 1;
	}
	return l;
}
int dp2(int s[], int low[], int n) {
	int ans = 0;
	for (int i = 0;i < n;++i)
		low[i] = 0x7fffffff;
	low[0] = s[0];
	for (int i = 1;i < n;++i) {
		if (s[i] > low[ans])
			low[++ans] = s[i];
		else {
            // 两个二分查找模板均可
			// int pos = bsearch(low, ans + 1, s[i]);
            int pos = bsearch2(low, ans + 1, s[i]);
			low[pos] = s[i];
		}
	}
	return ans + 1; // ans is the index of the last element
}

int main() {
	int s[MAXN];
	int f[MAXN];
	int n;
	cin >> n;
	for (int i = 0;i < n;++i)
		cin >> s[i];
	// int ans = dp(s, f, n); // 朴素dp
	int ans = dp2(s, f, n); // greedy + binary search
	cout << ans;
	return 0;
}

Dilworth定理

狄尔沃斯定理亦称偏序集分解定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。

在子序列问题中,可以如此理解,即:

把序列分成不上升子序列的最少个数,等于序列的最长上升子序列的长度.

把序列分成不下降子序列的最少个数,等于序列的最长下降子序列的长度.


利用该定理可以简化很多子序列问题.

P1020 导弹拦截

问题2就等价于求最长上升子序列的长度.