DP 套 DP
有这样一类问题：给出一个可以用 DP 解决的问题，求使得其问题的答案为某确定值的输入的方案数。
解决这类问题的思路主要是 按照某种方式（例如状态压缩）将所有 DP 的输入分类，然后用子 DP 将每一种类别的方案数统计出来。
Hero meet devi
定义基因串为仅由 ‘A’,’G’,’C’,’T’ 四个字符组成的字符串。给定一个长度为 $n$ 基因串 $S$ ，对于每个整数 $i\in[0,n]$ , 求长度为 $m$ 的基因串 $T$ 中使得 $\mathit{LCS}(S,T)=i$ 的个数。
注： $\mathit{LCS}(S,T)$ 表示 $S$ 和 $T$ 的最长公共子序列长度。
$n\leq15,m\leq1000$
设 $f_{i,j}=\mathit{LCS}(T_i,S_j)$ , 按照求 LCS 的经典 DP 方法，我们发现 $0\leq f_{i,j}-f_{i,j-1}\leq1$ , 可以状压。
我们设一个状态 $\mathfrak{S}$ 为 $S$ 中的选择的子序列，设 $F_{i,\mathfrak{S}}$ 表示前缀 $T_i$ 中与 $S$ 匹配位置集合为 $\mathfrak{S}$ 的方案数，那么可以用经典方法预处理出转移，得到 $F_{m,\mathfrak{S}}$ 后统计一下答案即可。
预处理的时间复杂度为 $O(2^n\sigma n)$ , 外层 DP 的时间复杂度为 $O(2^n\sigma m)$