[数据结构与算法]动态规划——不重复子序列DP法

动态规划——不重复子序列DP法

考虑一个基本模型：

给定一个字符串$S$，请问$S$中有多少个不重复的子序列。这里的子序列指，删掉$S$中某些字符，剩下的字符按照原有的顺序拼成的字符串。

容易想到一个基本的DP解法：

设$d{p}_i$为以$S_i$结尾（必选）的$S[1,i]$中的子序列的数量。特别的，设$d{p}_0=0$，对应一个空字符串。那么有如下转移方程：

$$d{p}_i=\sum _{j=0}^{i?1}d{p}_j$$

但是我们会重复进行记录相同的子序列，因此我们改变一下DP方程：

$$d{p}_i=\sum _{j=k}^{i?1}d{p}_j$$

则此问题的答案为${\sum }_{i=1}^{n}d{p}_i$。

其中$k$是满足$S_k=S_i$中最大的$k$，为什么这样可行呢？如果我们对小于$k$的$d{p}_j$进行计数的话，则这个子序列已经被$d{p}_k$所计数过了，因此加到上述和中必然会重复计数，加到$S_k$后面是可行的，因为我们对原有的子序列的末尾长度增加了一。

例题

ABC 214F