定义状态dpi,jdp_{i,j}dpi,j,代表以iii位字符为中心,111到i−1i-1i−1的子序列与从第jjj位的字符为开头的jjj到nnn中的子序列构成回文的方案数 那么当第jjj位与第i−1i-1i−1位匹配的时候,dpi,j=∑k=j+1k=lendpi−1,j+1dp_{i,j}=\sum _{k=j+1}^{k=len}dp_{i-1,j} +1dpi,j=∑k=j+1k=lendpi−1,j+1,然后我们就可以从后往前遍历,去掉 枚举k的这一维,这样子时间复杂度就可以控制在O(n2)O(n^2)O(n2)内 PS:这题的全部难度都在定义状态上,会定义转移方程式太好想...