Set analytical method
概述ψ(`∇´)ψ
这种方式和一般 DP 分析方式不一样的地方在于,
这种 DP 分析方式把 DP 的状态空间看作全集,一个个 DP 状态看作一个个小集合。
把决策转移变成了集合的划分,以达到不重不漏,并把 DP 状态拆分为了两种属性。
用三个线性 DP 的经典模型作例子说明。
LIS 问题ψ(`∇´)ψ
给定一个序列 \(a\) ,求它的最长上升子序列的长度。
\(|a| \le 3000\)。
本着问啥设啥的原则,我们设计的状态需要包含要素:”上升自序列,最长“。
一般来说,用来设计状态的 ”标志“都是 ”当前,最后“。
也就是说,状态一般都会设计成:“当前状态的什么什么信息,有什么什么属性”,或者 “最后一个状态的信息是什么什么,属性是什么什么” 的样子。
所以,设 \(dp_{i}\) 表示所有以 \(a_i\) 结尾的上升子序列组成的集合,属性为 Max。
那么如何处理转移?
将 \(dp_i\) 所代表的集合划分为多个子集,并且这些子集都可以利用一个状态来表示。
划分的依据则是 “最后一个不同的点”。
首先写出 \(dp_i\) 代表的集合是什么:“所有以 \(a_i\) 结尾的上升子序列”。
把 \(dp_i\) 这个集合包含的所有子序列展开,可以发现他们全部长成这样:
其中 \(las\) 表示这个子序列的倒数第二个元素。
发现 “最后一个不同的点” 就是这些倒数第二个元素 \(las\),因为所有子序列的倒数第一个元素都是相同的。
所以就以这些 \(las\) 作为划分依据,可以将集合 \(dp_i\) 划分如下:
图中橙色字体是代表了这个子集的状态,绿色字体说明了这个子集代表了什么。
划分完之后,观察 \(dp_i\) 这个集合对应的属性,是 \(\max\),所以我们要在所有划分出来的集合对应的状态当中取最大值。
可以得到方程:
但是注意到这些划分出来的集合不一定都能够转移到集合,比如存在一个 \(a_j > a_i,j < i\) 的逆序对,
那么 \(dp_j\) 这个集合就不可能转移到 \(dp_i\),因为 \(dp_j\) 代表了 ”所有以 \(a_j\) 结尾的上升子序列构成的集合“。
而这个集合中的任意一个子序列提出来,在后面接上 \(a_i\) 后,它都不会再是一个上升子序列了。
所以我们还需要判断划分出来的集合是否合法,方程变为:
而划分集合的时候发现, \(a_i\) 本身也能作为一个单独的上升子序列出现,所以初始化的时候要令 \(dp_i = 1\)。
方程变为:
把 \(+1\) 放进 \(\max\) 里是为了方便转移。
根据定义,答案是 \(\max\{dp_i\}\)。
可以写出代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
复杂度 \(\text{O}(n^2)\),每次划分枚举子集转移消耗 \(\text{O}(n)\),枚举以所有点作为结尾的情况消耗 \(\text{O}(n)\)。
本题所给的启示:
- DP 的本质是 ”聪明“ 地划分集合。
- DP 的初始化要根据状态本身的定义和转移需求来设置。
- DP 划分的重要依据是 ”最后一个不同点“,思考时需要考虑把当前集合展开。
- 划分出的子集不一定都能用来转移,要进行可行性的判断。
LCS 问题ψ(`∇´)ψ
给定两个序列 \(a,b\) ,求他们的最长公共子序列。
\(|a|,|b| \le 3000\)。
本题的要素是 ”公共,最长“。
考虑如何处理这个 ”公共“,发现我们要做的就是,找到一组 \(i,j\) 使得 \(a_i = b_j\) ,然后进行转移。
所以设 \(dp_{i,j}\) 表示由 \(a[1\sim i],b[1 \sim j]\) 构成的所有公共子序列,属性为 \(\max\)。
发现集合可以划分成两个部分,第一个部分是 \(a_i \not = b_j\) 时,由 \(a[1 \sim i],b[1\sim j]\) 构成的公共子序列。
第二部分是当 \(a_i = b_j\) 时,由 \(a[1 \sim i-1],b[1\sim j-1]\) 构成的公共子序列。
为什么是由 \(a[1\sim i-1],b[1 \sim j-1]\) 构成的呢?因为此时 \(a_i = b_j\) ,所以这半部分所代表的集合中的公共子序列都长成这样:
那么此时的答案就是前面部分的长度的最大值 \(+1\),而前面那部分长度的最大值实际上就是由 \(a[1\sim i-1],b[1\sim j-1]\) 构成的所有公共子序列的长度最大值,集合 \(dp_{i-1,j-1}\) 即可表示这一部分,所以实际上这部分是由 \(a[1\sim i-1],b[1\sim j-1]\) 构成的,只是转移时 \(a_i,b_j\) 会有贡献而已。
然后考虑第一部分,我们并没有办法对它用一个状态直接表示,所以再次对他进行划分。
因为 \(a_i \not= b_j\),所以我们分别把 \(a_i,b_j\) 踢出去,然后进行转移。
那么第一部分就可以划分成 \(dp_{i,j-1},dp_{i-1,j}\) 两个子集,因为 \(dp_{i,j}\) 的属性是 \(\max\),而转移时 \(a_i \not= b_j\),不能提供贡献,所以直接让 \(dp_{i, j}\) 继承 \(\max\{dp_{i,j-1},dp_{i-1,j}\}\) 即可。
划分如下:
可以得到方程:
根据状态定义,\(dp\) 应当全部初始化为 \(0\),答案为 \(dp_{n,n}\)
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
复杂度 \(\text{O}(n^2)\)。
本题所给的启示:
- 划分后的转移实际上是利用 ”子集“ 和 ”当前信息“ 的结合。
- 如果当前信息占用了集合的一部分,划分时应当把它刨掉。
数字三角形问题ψ(`∇´)ψ
为了方便叙述,此处换成了棋盘类 DP 的模板。
给定一个 \(n \times m\) 的矩阵,初始你在 \((1,1)\),每次可以往下或者往右走一步。
问走到 \((n,m)\) 的方案数。
设 \(dp_{i,j}\) 表示从 \((1,1)\) 走到 \((i,j)\) 的所有方案,属性为数量(注意这里变为了数量)。
考虑划分集合 \(dp_{i,j}\)。
展开 \(dp_{i,j}\) 中的所有方案,发现他们都长这样:
发现 ”最后一个不同点“ 就是 ”上一步“ 所处的位置 \((x,y)\)。
而本题要求只能向下或者向右,所以只有从上面和左面走过来两种情况。
所以集合可以划分成 \(dp_{i,j-1},dp_{i-1,j}\) 这两部分。
可以列出方程:
其中根据状态定义,\(dp_{1,1}\) 应当初始化为 \(1\),其它的应当为 \(0\)。
但是要注意判断是否越界,所以此时可以利用另一种 DP 方式,顺推。
也就是考虑把当前集合的方案数加到所有划分后直接含有它的集合的方案数当中。
开大数组后就不用判边界了。
所以可以得到新的方程:
初始化不变。
可以写出代码:
1 2 3 4 5 6 7 8 9 |
|
本题所给的启示:
- 不止可以划分后用子集来更新当前集合,也可以划分后用当前集合去更新让当前状态作为子集的集合。
- DP 的属性不止 \(\min,\max\),还有数量,期望,概率等。