学习笔记——线性动态规划

· · 算法·理论

线性动态规划是OIer学习DP的基础，只有学好了线性DP，才能更好的理解之后学习的背包、区间DP、树形DP等一系列难题，那么废话不多说，开始我们的学习之旅吧！

1.DP的概念

1.{\color{Red}\colorbox{White}{子问题重叠性}}：DP算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后，DP才会执行下一阶段的计算。

2.{\color{Red}\colorbox{White}{无后效性}}：为了保证DP中每一阶段的计算能够按顺序、不重复的进行，DP要求已经求解的子问题不受后续阶段的影响。

我们身为OIer自然要更加重视知识的关联性。运用类比的思想，我们可以发现DP与图论这两个看似毫不相干的两个知识竟然有着千丝万缕的联系。

3.${\color{Red}\colorbox{White}{最优子结构性质}}$： (1).${\color{Blue}\colorbox{White}{狭义理解}}$：**下一阶段的最优解能够由前面各阶段子问题的最优解导出**。 (2).${\color{Blue}\colorbox{White}{广义理解}}$：DP在阶段计算完成时，只会在**每个状态上保留与最终解集相关的部分代表信息**，这些代表信息应该具有**可重复的求解过程**，并能够**导出后续阶段的代表信息**。 4.${\color{Red}\colorbox{White}{总结}}

综上所述，状态、阶段和决策是构成DP算法的三要素，而子问题重叠性、无后效性和最优子结构性质是问题能用DP求解的三个基本条件。

2.线性DP的定义

如果一个DP算法的状态包含多个维度，但在每一个维度上都具有线性变化的阶段，则该DP算法称为线性DP。

3.线性DP的核心思想

首先，我们可以先用自己的方式进行题意简述，把握题目大意，再想好每一个状态的状态表示及阶段划分，并在此基础上推出状态转移方程，最后确定DP的边界条件及DP目标后就可以开始码代码了。（这里推荐画一个表格，这样更能一目了然地看出状态转移方程）。

举个栗子（LIS问题--最长上升子序列）

题意简述 给定一个长度为N的数列A，求数值单调递增的子序列的最长长度
状态表示 令F[i]表示以A[i]结尾的最长上升子序列的长度
阶段划分 子序列的结尾位置（数列A中的位置，从前到后）
转移方程 F[i]=\max(F[i],F[j]+1)(0 \leqslant j < i,A[j]<A[i])
边界条件 F[0]=0
目标 \max(F[i])(1 \leqslant i \leqslant N)

4.线性DP的一些优化技巧

1.在设计DP的状态转移方程时，可以以如何计算出一个状态 （直接）的形式给出，也可以考虑一个已知状态应该更新那些后续阶段的未知状态（间接）。它们各有千秋，视具体题目选择合适的方法更有利于解题。

2.滚动数组真的好用：我们对于一些可能MLE的DP状态进行分析，如果我们发现这一状态的DP只与前几状态的DP有关，就可以只定义这个数+1个的该维度空间（举个栗子：若i的状态只与i-1的状态有关，则对于i的维度可以只开到2的空间，循环使用0和1）。但是滚动数组会覆盖掉之前求的状态，如果只用求最终状态则建议使用滚动数组进行优化，若要求每一个状态的最优解，千万别用！（不过这类题一般不会爆MLE，要不然就无解了）（滚动数组具体用法参照T7我的代码）

3.在实现状态转移方程时，要注意观察决策集合的范围随状态的变化情况，若决策集合有规律的变化，就可以考虑维护一个新的变量记录决策集合的当前信息，避免重复扫描，把转移的复杂度降低一个量级。（要栗子的话就是T2我用优化打了个N方DP过了NlogN的题（与数据水也有很大的关系））

别问为什么没有代码，DP这毒瘤玩意根本没有模板

好了，最后我再扔几道题就闪吧！

1.线性DP的入门水题（一篇比较了DP与贪心、搜索、记搜复杂度的好题解）（码了个10min竞速代码）

通过这道水题，我知道了两点：

(1).我的手速真的不行，码代码码不快（慢慢练吧）

(2).没有立刻想到最优解（明显从下传到上比从上传到下更快，因为前者只用输出ans[1][1],而后者要多一个\Theta(n)的循环求最大值），要多锻炼自己的思维水平。

2.栈+二分、树状数组版二维偏序吊打DP的伪DP题（通俗易懂的栈+二分题解）（还不会的树状数组版二维偏序）（DP思路+DP常数优化+我的代码）

3.正反两遍最长上升子序列的水题（题解）（我的代码）

4.做两遍线性DP的水题（题解）（我的代码）

5.四种牌分别处理的线性DP（有点背包的味道）（讲的不错的题解）（我的代码）

6.第一个自己独立做出的DP绿题（O(N)做法的题解）（二分做法的NlogN的题解）（我的代码）

7.滚动数组+三维DP（讲的很详细的题解）（我的代码）

随手取模真的很重要，不然100pts->60pts。以后遇到这类题也不用太慌，先明确自己设定的DP数组每个维度都代表着什么（最好在代码中的相应数组下写一点注释），然后考虑未知的状态可以由那些已经求出的状态推出（可以在草稿纸上写出DP方程式），明确思路后再码代码。

8.构造新数列求最长不下降子序列+推新结论的恶心题（有动图的良心题解）（码了半天的代码（一个晚上+半个上午））

比较难的DP题真的就是在比耐心和细心。

问题一：本题运用正难则反的思想，对于暂时毫无思路的问题，可以考虑构造新数列进行求解（可以将题面简化为一堆关系式，然后对其进行化简，找出关系式中的共同点，在将其用一个新数组存储，可以极大的简化代码、降低复杂度和辅助思考）。

那个推新结论是人能想到的吗？

问题二：对于一些更难的问题，可以多画图辅助思考，排除一些矛盾的情况，找到一些类似的情形，然后转化为DP的形式进行状态转移方程的推导。

9.第一道独立做出的DP紫题（当然要写一篇题解好好庆祝）

10.双DP数组+前缀和优化的水题（讲的不错的题解（只看思路就可以打代码））（我的代码）

最后再挖两个坑，以后再填吧！（毕竟现在不是刷黑题的时候）

1.学完高数再做的黑DP

2.打完猪国杀之后用耐心做的大模拟+DP