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

那么当第jj位与第i−1i-1位匹配的时候,dpi,j=∑k=j+1k=lendpi−1,j+1dp_{i,j}=\sum _{k=j+1}^{k=len}dp_{i-1,j} +1,然后我们就可以从后往前遍历,去掉

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

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

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