题解 | #回文子序列计数#

定义状态$d{p}_{i,j}dp\_\{i,j\}$,代表以$ii$位字符为中心,$11$到$i-1i-1$的子序列与从第$jj$位的字符为开头的$jj$到$nn$中的子序列构成回文的方案数

那么当第$jj$位与第$i-1i-1$位匹配的时候,$d{p}_{i,j}={\sum }_{k=j+1}^{k=len}d{p}_{i-1,j}+1dp\_\{i,j\}=\backslash sum\; \_\{k=j+1\}^\{k=len\}dp\_\{i-1,j\}\; +1$,然后我们就可以从后往前遍历,去掉

枚举k的这一维，这样子时间复杂度就可以控制在$O(n^2)O(n^2)$内

PS：这题的全部难度都在定义状态上，会定义转移方程式太好想了

代码可以直接看别人的提交，目前还没看到用这个以外方法做的