dp进阶之路(二)——线性dp（1）

一点说明

个人其实对线性dp、区间dp、背包dp这样的分法有所怀疑，因为有的题真的很难说清楚是哪一类，但不可否认的是，对于初学者入门来说，这样分是很愉快的也是很有用的。然而我需要提醒大家的是，不要被这些分类束缚了思路，“阵而后战,兵法之常,运用之妙,存乎一心”，如果分类的讲解就是阵法的话，做题就是运用，你需要做的是了解它并超越它！

线性dp的经典例题有：最长上升子序列（LIS），最长公共子序列（LCS），最大子串和等等（本文的前置知识，需要大家自行学习）。在会了这几个题之后我们就可以来看今天的问题啦!

例1：三个串的最长公共子序列

题意： 给你三个串， 求其最长公共子序列，输出最长公共子序列的方案。

思路：
两个串的时候我们需要分别记录每个串是用的前多少个字符来求最长公共子序列，三个串也一样——给状态加一维：f[i][j][k] 表示三个串前i，j，k个字符所能组成的最长公共子序列的长度

方程是显而易见的： f[i][j][k] =max (f[i-1][j][k],f[i][j-1][k],f[i][j][k-1])
如果 s1[i]，s2[j]和s3[k]一样，那么：f[i][j][k]=max (f[i][j][k], f[i-1][j-1][k-1]+1)

但是这个是求长度，题目要的是方案，dp最常用的记录方案（或者方案数目）的办法是开一个数组，和dp的数组同一个结构（我在本题的描述中设dp的数组为f， 方案的数组为g），在f数组发生转移的时候同时用g来记录当前状态是从哪里转移过来（或者是到当前状态的方案数目），那么，只需要在求出最后结果后回推回去就可以求出方案了（方案数就直接得出）。
不过对于这个题来说这样做是有点麻烦的了，为什么这么说？因为每个状态是有三个参数的（那么g最好是个struct类型，记录三个值），然后转移又是四种情况，对应生成答案的方法还不一样，总之不是很好写的（可以尝试但是并不推荐）。

那么这个题有没有其他方式呢？
直接把f[i][j][k]搞成一个字符串……然后状态直接对应方案……
至于判断从哪儿转移的时候要用到最长公共串的长度不就可以通过这个串求length得到么？

小结：
Q：为什么在一般的dp记录方案中g不直接表示方案？
A：因为随着状态的转移转移方案往往越来越复杂（越来越长，包含的信息太多），在大部分情况下实在是太不实用。（注：不要轻易的说一个方法不能，但也不要因为能就一定要用它，多思考，综合比较，具体情况要具体分析！！）

Q：为什么这个题可以？
A：方案是一个字符串，可以很容易储存且这个字符串又可以表示全部用于转移的信息（长度），所以直接存就可以了！！

例2：NC15553 数学考试

题目链接：数学考试
来自：3月27日每日一题 （变形四为新添加）

因为长度已知，最暴力的办法肯定是直接枚举两个子区间的起点，然后求和，复杂度。

连续区间求和可以用前缀和来优化，即用sum[i]表示数列前i个数字的和，那么，而区间[l,r]的和则可以表示为。这样优化之后就不用遍历求和了直接算就好，时间复杂度变为

实际上我们根本不用枚举右边子区间的起点，因为如果我们的选择的左边这个区间是[l,r]的话，右边的区间一定是r右边的所以长度为k的区间里面和最大的那个，这个只需要从右往左扫描一遍就可以维护出来——如果我们用maxn[i]表示i右边的所有长度为k的区间的和的最大值，那么（要么是i+1右边长度为k的区间的最大值，要么是从i开始向右长度为k的区间）。
(看起来似乎不像dp，但是实际上前缀和也好，维护maxn数组也好都是使用的dp的思路)
这样子了。

给大家提出几个变形的相关问题：

变形一：不限制长度——在一个数列里找两个不相交区间使得他们权值和最大

如果思路还和刚刚一样，如果我们用maxn[i]表示i右边的所有子区间的和的最大值的话 ，显然如果要让尽量大，j一定会取sum[j]最大的那个，所以再维护一个数组maxsum[i]表示i之后sum的最大值即可。

但是这样的话你会发现由于区间的长度不固定了，我们在枚举左区间的时候是需要枚举两个端点的，复杂度又回到了，事实上这也不需要，我们其实只需要枚举左右区间的分界点，即用另外一个数组维护一个i左边所有子区间的最大值（这个过程和上述过程是对称的），然后分界点左右区间最大值相加即可。

另外，维护i右边的所有子区间的和的最大值还有一种办法，这是使用的动态规划的思想——用f[i]表示必须要选i的情况下i向右最大的区间和，，然后。（即最大子串和）

变形二：区间数目变多——找m个长度为k的不相交区间使得他们的权值和最大()

这个时候就必须要上动态规划了。
f[i] [j]表示前i个数已经选了j个长度为k的不相交区间的最大权值和。

你可能会得到这样一个转移方程：即在前p个选了j-1个区间的基础上选区间[p+1,p+1+k-1]这个长度为k的区间。
（如果你得的方程是的话，那么恭喜你，下面四段你都可以跳过了。）

这个的复杂度是的，显然很难令人满意。
我们可以先把以x结尾的长度为k的区间的和维护到一个数组sumk[i]里面，，但是这似乎并没有在时间复杂度上有什么实质性的优化，但再认真观察这个转移方程你会发现实际上是一个前缀最大值。当i增加1的时候，对应的p也会增加1。

如果我们在算f[i] [j]之前先把f数组的第j-1列全部算出来（这个是可以的，按行转移和按列转移都是可以的）并且在算第j-1列的f值的同时把对应的加进去，即维护一个数组来存，再维护出这个数组的前缀最大值，状态转移的时候就不需要枚举p了。算法时间复杂度变成了 ,问题得到解决。这是通过观察可以转移过来的区间有什么性质来优化掉转移过程中的枚举。

但是事实上真的需要这么麻烦么？仔细分析你会发现“在前p个选了j-1个区间的基础上选区间这个长度为k的区间”这个操作中，除了选以i为右边界的这个长度为k的区间的方案，其他的方案都是包含在中的，也就是说，枚举p完全是多余操作……其实说白了，每次转移我们只需要考虑第i数个选还是不选，要选它就要选它以前的k-1个数构成一个连续的k个数的区间；不选它，那扔掉就好。

这就告诉我们，推动态规划的时候要注意，要避免重复地枚举前一步的状态，对于有些题来说状态枚举重复了这个事情可能并不明显，但当你发现复杂度不行的时候，也不要轻易就否定它重启炉灶，多想一想，你其实有很多种方法来解决问题！

变形三：区间数目变多且不限制长度——找m个不相交且长度不限的区间使得他们权值和最大()

有了前一个题的经验，我们还是用表示前i个数里已经选了j个不相交区间的最大权值和，还是考虑第i个选不选。这个时候一个小问题出现了，如果我们要选a[i]，选中的区间数究竟是会+1呢还是不变呢？也就是说，我们不知道第i-1个数选没选所以没法转移……那怎么办？我们在状态的描述中强行规定表示第i个数必须要选且前i个数里已经选了j个不相交区间的最大权值和，既然第i个数必须要选了，那么 即a[i]可以接在上一个区间后面，或者成为一个区间的第一个元素。

还是刚刚那个问题，我们并不想要枚举p，而这个式子含有p的部分也正好是f数组上一列的一个从1开始的连续区间的最大值，i加1的时候p也相应加一，所以对上一列求一个前缀最大值即可。即我们在转移的时候维护一个数组表示f数组第j列前i个数的最大值，即所有的满足的的最大值 。所以 。注意：需要先按列转移，即j的循环在外层。

这里有一个小技巧：当状态转移方程中等式右边包含一个区间的最值，且这个是区间一个端点固定另一个端点随着转移而递增的，就可以用前缀最值来维护，同样的情况，如果是求和，就用前缀和来维护。对于学有余力的同学，这个技巧还可以扩展：如果是一个等式右边是一个定长连续区间的最值，那么是可以用单调队列的来维护的。

在每日一题的题解中@iamhpp 同学关于变形三有更加简单而清晰的方法：
设 表示前 i 个数，分成 j 段，第 i个不选/选的最大值，转移方程：

就没有之前的需要求前缀最大值的问题了，为什么？

因为在上面的所有的 中 除了 ，其他的所有情况就是前i-1个数分成j段，第i-1个不选的最大值，也就是的值，换句话说 ，这一部分其实就是上面的，就是上面那个前缀最大值的一部分。

实际上，这位同学的状态才是这个问题严谨而完整的状态，二维状态，表示第i个数必须选的情况下前i个数里已经选了j个的不相交区间的最大权值和时，实际上是将不选i的情况省略掉了，这种省略有的时候是可以省掉可算可不算的部分，但是在这个问题里，显然这种省略其实反而使得转移的时候麻烦了起来。

也就是说我们在求解最大子串和还有最长上升子序列时使用的f[i]表示第i个元素一定要选的最大xxx其实也是非完整状态，因为不影响转移没必要计算它他们把第i个元素不选的状态丢了，当如果需要算的时候请你不要忘记他！

但是各位同学，即使你定义的可能是个不完整的状态且导致出现了一些本可避免的麻烦，你其实还是有办法优化回去的，最后，优秀的算法们会殊途同归！

变形四：区间数目变多不限制长度且首尾相连——在首位相接成一个环的数列中找m个不相交且长度不限的区间使得他们权值和最大()

一般我们对付首尾相接的问题有两种办法：特判首尾或者枚举断点。（把原数组复制一遍也是常用的，在区间dp当中使用尤其多，但是这种办法的实质就是枚举断点，只是把枚举断点的操作放到了最后求答案的时候。）

回到这个问题，枚举断点的话会增加复杂度数量级，因为它没法做到区间dp那样限制住起末位置
（f数组里面只有右界信息没有左界），所以我们考虑特判首尾的方法：

其实选m个不相交区间有两种可能：
选的区间不跨越首尾——那就是原来的求法；
选的区间跨越首尾——可以认为是选了m+1个区间，第一个数和最后一个数都必选
如果f[i][j]还像刚刚那鱼表达前i个数i必须选，一共选了j个区间的最大和
那么f[i][1]其实就是数组前缀和，这样第一个就肯定选上了，之后的dp和变形三一样，最后f[n][m+1]的值就是答案。