题目链接：https://www.acwing.com/problem/content/897/
讲解
动态规划问题具有三个特质：
- 子问题重叠: 即子问题是相互之间依赖的 这个子问题在之后可能被反复使用
(此条件并非必要条件 但失去它也就没有优化作用了） - 最优化原理: 此问题可以通过子问题的代表元素（最优解）来求出 这就也称作满足了最优子结构
- 无后效性: 此状态一经确定 不受以后决策影响
通过例子来慢慢解释
\(LIS\)： 给定一个长度为\(N\)的数列，求数值严格单调递增的子序列的长度最长是多少。
我们可以写出暴力程序:
int n, a[105];
int k[105], ans;
void dfs(int len) {
if (len > ans) {
ans = len;
// 如果需要方案，记录 {A[k[1]], A[k[2]], ..., A[k[len]]}
}
// {k[1], k[2], ..., k[len]}
// B = {A[k[1]], A[k[2]], ..., A[k[len]]}
for (int i = k[len] + 1; i <= n; i++)
if (a[i] > a[k[len]]) {
k[len + 1] = i;
dfs(len + 1);
}
}
k[0] = 0, a[0] = -(1<<30);
dfs(0);
我们可以发现 对于每一个\(dfs\) 只用到了\(k[len]\)这个结尾数
于是我们可以不用记录\(k[]\) 直接记录上一个数
void dfs(int len, int tail) {
if (len > ans) {
ans = len;
}
for (int i = tail + 1; i <= n; i++)
if (a[i] > a[tail])
dfs(len + 1, i);
}
a[0] = -(1<<30);
dfs(0, 0);
于是这时候我们就发现了 我们总是去调用\(tail\)值同样的函数
if a[] = {1, 7，3, 4, 5};
调用了两个函数 k[]为
{1，3，4}
和 {3，4}
那么我们发现 其实没有必要调用{3, 4} 无论后面接什么数 他一定不会比{1, 3, 4}优
但是他们的\(tail\)相同 \(len\)不同 我可不可以把他们归为一类 只要调用到\(tail\)值为4 那他以\(4\)结尾\(LIS\)最大就是\(3\)（最终问题不就是求最大值吗）
那么我们需要换一下枚举方法
那么此时的答案 是不是就是 每个以\(a[i]\)为结尾的最长上升子序列的长度的最大值 的 最大值
由此：
新状态：结尾下标
状态总数：\(n\)
\(f[i]\)表示以\(a[i]\)为结尾的最长上升子序列的长度
显然子问题之间满足最优子结构性质 并且
按照1-n枚举是拓扑序（1.不可能有环（反证） 2.不可能由后面的更新前面的(LIS定义)）
那么当枚举到i时 他只能被前面的更新 但是前面的更新完了 所以他就是最大值
(这就是\(f[i]\)求法 以\(i\)为结尾的\(LIS\) 上一个数一定是 \(1 - i - 1\)结尾的满足条件LIS 最大值 通过前面数更新)
然后再去遍历拓扑图 看看后面能接什么 枚举就行
由此
f[0] = 0;
for (int i = 0; i < n; i++) // i: 结尾下标
for (int j = i + 1; j <= n; j++) // 下一个数
if (a[j] > a[i]) f[j] = max(f[j], f[i] + 1);
也可以枚举这个\(f[i]\)是由什么转移来的
f[0] = 0;
for (int i = 1; i <= n; i++)
if (int j = 0; j < i; j++) // 前一个数
if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
完整代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1010;
int w[N], n, f[N];
void read(int &r)
{
int f = 1, x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
r = f * x;
}
int main()
{
read(n);
for (int i = 1; i <= n; i ++ ) read(w[i]);
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (w[j] < w[i])
f[i] = max(f[i], f[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++ )
res = max(res, f[i]);
printf("%d\n", res);
return 0;
}