学习笔记：基础动态规划
线性 DP
定义
具有线性“阶段”划分的动态规划算法被统称为线性动态规划
入门线性动态 DP
LIS 问题
最长上升子序列问题。
问题：给定一个长度为 \(N\) 的数列 \(A\), 求数值单调递增的子序列的长度最长是多少（子序列不需要连续）。
经典的线性动态规划问题。
分析：容易发现，对于某一个位置 \(i\)，其所处的最长上升子序列一定是 \(i\) 前面的最后一位小于 \(A_i\) 的最长的上升子序列。
状态：定义 \(f_i\) 表示以 \(A_i\) 为结尾的"最长上升子序列"的长度。
阶段划分：子序列的结尾的位置（从前往后，这明显是线性的）。
状态转移方程：$$f_i = max_{0 \leq j \lt i, A_j \lt A_i}(f_j + 1)$$
初始化：\(f_0 = 0\)。
答案：\(max_{1 \leq i \leq N}(f_i)\)。
时间复杂度：\(O(N^2)\)。
LIS 问题有 \(O(N \log N)\) 的做法，不过与 dp 关系不大。
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e5 + 5;
int N, A[MAXN], f[MAXN], ans;
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
for (int i = 1; i <= N; i++)
for (int j = 0; j < i; j++)
if (A[i] > A[j]) f[i] = max(f[i], f[j] + 1);
for (int i = 1; i <= N; i++) ans = max(ans, f[i]);
printf("%d", ans);
return 0;
}
参考资料
《算法竞赛进阶指南》 李煜东