线性dp | MarkCup

本篇将介绍线性dp

介绍

动态规划又称为DP，作为重点基础算法之一，有很多拓展的用法和优化思路，我会分多篇进行讲解。
本篇会介绍dp的基本思想，以及动态规划最基础的用法————线性dp。

引入

当我们通过枚举计算答案的时候，会发现其中有一段数据被重复计算。
我们将其存下，后续只需要在其基础上进行修改，即可快速计算出结果。
例如： $1+1+1+1+1+1+1+1 = 8$ 再 $+1$ 等于 $9$
可以发现，我们保存了之前的结果，在之前的结果上进行计算，速度显著提高。
这就是动态规划中所谓的状态

当我们保存了每个子问题的状态的时候，可以发现他们之中有一些特定关联。
使用一个计算公式，可以根据之前的状态得出当前的状态。
这就是动态规划中所谓的 状态转移方程

DP题目特征

当我们发现以下特征的时候，可以考虑寻找题目中的状态和 状态转移方程 ：

最优子结构

意为：当前状态的最优解，可以由子问题的最优解推出

DP类似于贪心，反复将局部最优解向后推，得到全局的最优解。
当出现 ”局部最优解并非全局最优解“ 的情况时，需要检查是否有别的条件需要考虑入状态，或者使用其他的方式解决题目。

这个条件保证了题目中的状态可以被递推解决

无后效性

意为：当前状态的选择，不会受到后续状态的影响

将局部最优解向后推时，如果当前状态会影响到之前状态，那么需要将之前的状态更新，更新后又需要重新推。
这样会导致状态反复更新，反复得不到全局最优解。

这个条件保证了题目中的递推不会循环。

重叠子问题

意为：在递推过程中，相同的子问题会被重复计算

由于DP会记忆之前的状态，用于后续计算，所以当有重叠子问题的时候，计算效率会被提高。
例如斐波那契数列，如果暴力计算，每个新状态需要重复计算旧状态的内容。
如果子问题不重叠，使用分治的方案会更快。

列子

最长上升子序列

题目描述

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 $n$ ，表示序列长度。

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数表示答案。

输入输出样例 #1

输入 #1

1 2	6 1 2 4 1 3 4

输出 #1

说明/提示

分别取出 $1$ 、 $2$ 、 $3$ 、 $4$ 即可。

来源：洛谷B3637

针对这个例题，暴力方案是使用 $O(2^n)$ 的时间，枚举每个数字是否选择。但是这个以指数级上升的时间复杂度是完全不可接受的。

我们注意到每个数字都需要进行选择，且每个选择的最优情况不会受到后续影响。