至多删除三个字符(天梯赛)
分析
一看就知道是个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;
}
}