最长上升子序列是使用动态规划求解的经典题目。
B3637 最长上升子序列
1. 题目描述
给定一个长度为N的数列(w[N])，求数值严格单调递增的子序列的长度最长是多少。
2. 动态规划
使用动态规划的核心是构造状态转移表达式，先来看看这道题目是如何定义状态及转移方程的。
定义f[i]表示以w[i]结尾的最大上升序列长度，则在w[i] > w[j]时，f[i] = max(f[i], f[j] + 1)，j=0,1,2,…,i-1。上面这种情况的时候要更新状态是不难理解的，但是这也导致f[i]是由小于i的最优解通过增加w[i]产生的，有没有可能f[i]是由小于i的非最优解产生的呢，也就是说在w[i] <= w[j]时，f[j]也存在信息，可以用于产生最优解，其实仔细想一下这种情况就是去除w[j]后的上升子序列加上w[i]构成的，那么一定会存在一个对应于w[i] > w[q]，并使用f[i] = max(f[i], f[q] + 1)进行更新，所以在w[i] <= w[j]时是不用再进行更新的。
下面看一下代码。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
using namespace std;
int n;
int w[5010]; //输入序列
int f[5010]; //状态记录
int main() {
ios::sync_with_stdio(0);
cin >> n;
for(int i; i < n; i ++) {
cin >> w[i];
}
int mx = 1;
for(int i = 1; i < n; i ++) {
f[i] = 1;
for(int j = 0; j < i; j ++) {
if(w[i] > w[j]) {
f[i] = max(f[i], f[j] + 1);
}
}
mx = max(mx, f[i]);
}
cout << mx;
return 0;
}
动态规划的代码总是很简洁明了，但是想出来思路就很难，特别是第一次遇到某个题目。
3. 输出一个最长上升子序列
根据f[n]状态记录数组的定义，可以从小到大依次输出状态记录分别为mx,mx-1,…,1。最长上升子序列显然是可能不唯一的，下面的代码只输出一个。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int mx = 1, pos = 0;
for(int i = 0; i < n; i ++) {
if(mx <= f[i]) {
mx = f[i];
pos = i;
}
}
// 输出一个最长上升子序列
int *num = new int(mx);
num[0] = w[pos];
int cnt = 0;
for(int i = pos - 1; i >= 0; i --) {
if(f[i] == mx - 1) {
num[++ cnt] = w[i];
mx --;
}
}
for(int i = cnt; i >= 0; i --) {
if(i < cnt) {
cout << ' ';
}
cout << num[i];
}