很容易想到一个状态\(f[i][j][k]\)表示\(A\)串前\(i\)个，\(B\)串前\(j\)个，从\(A\)中取了\(k\)个子串的总方案数
但是稍微推一下状态转移方程就可以知道这个时间复杂度和空间复杂度都会爆炸，其中时间复杂度为\(O(nm^2k)\)
空间复杂度可以用滚动数组来优化，所以我们先放下不管，我们先来考虑时间复杂度怎么优化
状态肯定是类似的，没有其他很多的选择，所以我们要微调状态
这个时间复杂度之所以会多一个\(m\)，就是因为我们在推方程的时候，要枚举互相匹配的\(A\)末尾的一段与\(B\)末尾的一段的长度
所以我们微调状态为\(f[i][j][k][0/1]\)，其中\(0\)表示不选\(A[i]\)，\(1\)表示要选
这样就可以把多一个\(m\)消掉
然后用滚动数组优化就可以了
总结一下我们目前遇到的微调状态：前\(i\)个（LCS问题），前\(i\)个且以\(i\)结尾（LIS问题），前\(i\)个且第\(i\)个可以选也可以不选（本题）
如果是两个串就是以上状态的排列组合
标签：子串,状态,个且,复杂度,不选,串前 From： https://www.cnblogs.com/dingxingdi/p/17974397