本篇将介绍线性dp

注意

动态规划类算法需要经过刷题才能完全领悟，大多DP题目都有固定的格式，我推荐在刷题中来逐渐了解DP的习性

介绍

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

引入

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

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

DP题目特征

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

最优子结构

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

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

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

无后效性

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

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

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

重叠子问题

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

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

接下来我会为你展示一个DP的例子，但是还是希望读者能够自行去训练题库，熟练掌握dp的使用方法

列子

最长上升子序列

题目描述

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

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

输入格式

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

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

输出格式

一个整数表示答案。

输入输出样例 #1

输入 #1

1
2
6
1 2 4 1 3 4

输出 #1

1
4

说明/提示

分别取出 11、22、33、44 即可。

来源：洛谷B3637

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

我们注意到每个数字都需要进行选择，且每个选择的最优情况不会受到后续影响。
因此，我们可以大胆假设状态为遍历到当前数字时，最长的可能。
由此可以推断出，状态转移方程为：dpi=max⁡{dpj+1}(1≤j<i∧aj<ai)dp_{i} = \max\{dp_{j}+1\}\quad (1 \leq j < i \land a_{j}<a_{i})

但是我们可以发现这样的方案的时间复杂度是 O(n2)O(n^2) 这实在是太无法令人接受了

![NOTE] 贪心+二分 解法

定义一个数组 d[N]d[N] ，其中 d[i]d[i] 表示长度为 i+1i+1 的上升子序列的末尾数字的最小值
可以发现，这个数组具有如下性质：

  • 数组中每个数严格递增，否则后一个数将会取代前一个数
  • 数组本身就是当前情况下，最长的上升子序列

已知这个数组维护的是最长上升子序列，在得到新的数字的时候
需要将其在数组中二分查找第一个大于或等于他的数字的位置
如果没有找到，则说明他可以延长这个最长上升子序列，于是将其放在末尾位置
如果找到了，则替换那个数，使后面的数字能够更加容易的往后延长

当遍历完所有数字后，这个数组的长度即为答案

由方法可知，该方案的时间复杂度为 O(nlog⁡n)O(n \log n) ，实在太过精妙