学习笔记：基础动态规划

线性 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 N = 1e5 + 5;

int N, A[N], f[N], 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;
}

参考资料

《算法竞赛进阶指南》 李煜东