建议升蓝

rt，本题dp不好想，状态定义形式

f[i][j][k][0/1]

，转移也要分4种情况（dp数组2x字符是否相等2）讨论，特别是

A_i=B_j

时的

f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k][0]

直接这么写还会炸空间，得用滚动数组处理压缩空间。

这道题真的是我见过的最综合的 dp 题目了。不但考察了线性 dp 的状态和转移设计，还有预处理优化，还融合了差分技术，还要用到滚动数组这种压缩空间的技术。（摘自ylch的题解）

一个能耗我好几个小时的普通dp。我感觉我在做这题时，一开始大部分时间做的都是无用功，选择一种合适的方法入手才相当于真正开始做这题，当然找对了切入点这题就一点不难。（啊嘞嘞嘞嘞的题解）

讨论操作