至多删除三个字符(天梯赛)


分析
一看就知道是个dp
很明显的转移方程:
dp[i][j]+=dp[i-1][j-1]+dp[i-1][j];
但是因为可能会有重复字符,导致两种不同的删除方法最后结果可能会是一样的
这个时候怎么办呢?
可以考虑转移方程再改一改条件,但是思来想去真的不好写
正面不好写那就反向写
考虑容斥,我们只要减掉重复的即可
因为重复的只可能出现在j的范围内

点击查看代码
for(int k=i-1;k>0&&j>=i-k;k--){
                if(s[i]==s[k]){
                    dp[i][j]-=dp[k-1][j-(i-k)];
                    break;
                }
            }
每次只要减掉最后与i相同的字符即可 因为我们这个是递推,前面的dp[][]已经是容斥过了,已经是答案了