【Tai_mount】 算法学习 - 线性动态规划 - 子序列问题的DP意义

VeritasDaLao教了我这东西一整个下午+半个早上，终于学会乐。

做完导弹拦截/最长公共子序列以后我问Veritas：为什么我不觉得这是DP，而它们出现在luogu的“线性动态规划”题单中。

原来是我跳了N^2直接看到第一个题解……所以没经过DP的那个思路。

他还给我推荐了一篇博客：​​https://www.luogu.com.cn/blog/pks-LOVING/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie​​

LIS问题

LIS问题就是最长上升（不下降）子序列问题，也可同样推广至“下降/不上升”。

给定seq[]长度为n的序列，要求输出LIS（最长上升子序列）的长度。

有两种做法如下：

做法一

dp[i]：seq[1~i]的LIS长度。

转移方程：dp[i]=max{dp[k]+1} (k<i&&a[k]<a[i])

这个想法很自然，外层循环i=1n，内层循环k=1i-1,if(a[k]<a[i]) dp[i]=max(a[k]+1,dp[i])

注意一点，初始赋值应为dp[1~i]=1，无论如何dp[i]最小都为1

dp[n]即为最后答案。

现在的算法是O(N)*O(N)，通过树状数组/线段树可以把内层优化成logn。

写这篇博文的时候有段时间没复习过线段树了。（我的线段树也是Veritas教的呢太感谢他啦）所以先省略这部分。

之前记笔记在有道云记的，一会儿再把线段树的笔记发上来。

做法二

就是这个做法让我想了一下午加半上午

dp[i][j]：该序列前j个数，长度为i的LIS序列的末尾元素的最小值

转移方程：

dp[i][j]=min{dp[i][j],a[j]} (dp[i-1][j-1]<a[j])

dp[i][j]=min{dp[i][j],dp[i][j-1]}

dp数组均赋初值为INF(无穷大)

我们所求为 max{i}(dp[i][n]!=INF)，这和题目意义是一样的。dp[][]=INF意味着没更新到，就是不存在那个子序列。我们要找的就是有意义的，最长的子序列

我们来画一张图：

红格子是我们想要更新的格子，就是那个dp[i][j]（此处i=j只是特例，标上数字只是为了更形象化）

它首先一定可以由dp[i][j-1]，即橙色格子转移而来（讨论的前提是dp[i][1]能被更新到哈~），这样红格子初值为INF，橙必比红小，通过dp[i][j]=min{dp[i][j],dp[i][j-1]}，就使得橙，红一样了。

而后考虑，可以由黄更新而来，前提是绿<黄。

（感觉上面有点说废话）

黄那一列都是已知条件，所以红只需要我们先推出来绿，橙就可以了，其他白格子都是不需要的，可以被覆盖（类似01背包），绿和橙的j相等，在同一行里，这意味着我们可以把表格缩成一行，变成一维的，dp[i]。

这意味着我们不能在红之前更新红左边的白，因为这会把绿覆盖过去，所以我们必须外层j循环内层i循环且i倒序。

……我这个地方蒙了好久，莫名，以后记住只要画张图就清楚了。

缩成一维以后就是这样：

同一个j1，可能会更新若干个dp[i]。如果它更新了若干个dp[x1]……dp[xn],且xn>……>x1。此时dp[x1……xn]=a[j1],对于x1……xn,后面一定是要一起更新x1+1,x2+1……xn+1的，要不大家都不能更新，要不然都更新。因为他们的dp[x]值都一样，我们更新时的判断就是只看dp[x]的值。

如果大家都不更新，自然大家都没用可以丢了，如果大家都更新了，我们发现xn更新出来的xn+1>x(n-1)+1>……>x1+1。谁可能会是答案呢？只有可能是xn+1，我们要取的是下标的最大值啊……那怎么更新后面缀着的x1……x(n-1)都不可能把答案更新出来，所以他们就可以去死了。或者说，我压根就不想生出来他们。

我是倒序枚举的i，遇到的第一个满足条件的然后break就好。后面的不用管，没用。

内层循环我们可以理解为：我们其实在求dp[]这个序列里从右往左数的第一个小于a[j]的。

接下来是另一个性质：

首先刚开始dp[]是单增的（全是INF），若某次a[j]更新了dp[i]，就说明a[j]>dp[i-1]，此时dp[i]被更新，更新出来最小也是a[j]。所以dp[i]>dp[i-1]。

单增的序列，求从右数第一个小于a[j]的数，然后把它后面第一个数换掉……这样就可以二分logn的复杂度了……呵呵呵呵呵呵，这不是从左数第一个大于等于a[j]的数换掉嘛……外层循环还是从1~n，所以我们发现：

和上一篇博文的程序一样了！

但我们知道为什么它是一个动归了。。

神奇！！！！