导读 ^ _ ^
子序问题是非常经典的线性DP问题。
本文将讲解最长上升子序列问题。
同时延申问题，探讨如何保存下来子序列。
最长上升子序列
思路
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
f[i] = 1;//只有一个的时候。
for(int j = 1; j <= i - 1; j++)
if(a[i] > a[j]) f[i] = max(f[i],f[j] +1 );
}
int res = 0;
for (int i = 1; i <= n; i++) res = max(res,f[i]);
cout << res << endl;
return 0;
}
如何输出序列呢？
其实实现方法非常简单，只需要记录转态转移的发生。
即，有转移，就记录下来转移源。
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int g[N];//记录状态转移源
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
f[i] = 1;//只有一个的时候。
for(int j = 1; j <= i - 1; j++)
if(a[i] > a[j]) {
if(f[i] < f[j] + 1) g[i] = j; //记录状态转移
f[i] = max(f[i],f[j] +1 );
}
}
int k = 0;
int res = 0;
for (int i = 1; i <= n; i++) {
if(res < f[i]) k = i;
res = max(res,f[i]);
}
cout << res << endl;
//逆序输出
for (int i = 1,len = f[k]; i <= len; i++) {
cout << a[k] <<" ";
k = g[k];
}
return 0;
}