poj 3267 最少需要删除多少个多余字符来匹配字典中的单词
这是一个动态规划的题，刚开始不容易想到，但是弄明白之后就很简单了，关键是在于状态规划方程
设dp[i]表示从单词开始位置到当前i位置之间至少要删除的多余字符
那么有这样一个方程
dp[i]=min{dp[i-1]+1,dp[pos+1]+(i-(pos+1)-len)};
其中dp[i-1]+1还是很好理解的，没有匹配的单词从上一个位置递增1
然后dp[pos+1]表示匹配到字典中的单词了，然后游标跑到字符串中匹配的单词最开始的位置，在这个地方dp[pos+1]表示在这个位置之前最少多余的字符数
接下来，我们不是已经匹配成功一个单词了么，但是在原串中这个单词不一定是连续的，就是有杂音，所以中间那些杂音就是多余的字符，怎么计算这些多余的字符呢
就是咱们从i位置开始从后向前匹配的过程中，i减去匹配到的开始位置，然后减去字典中这个单词的长度len，那么余下的就是多余的字符啦，加上这些多余的字符数
然后取上式两者中的最小值，就是到当前i位置所需要去除的最小多余字符的数目了
最后输出dp[L]即可（不知道有没有解释清楚，各位看官见谅，不懂的地方欢迎提问~）
下面是我的源代码：
#include<iostream>#include<string>using namespace std;char dic[605][30];char word[305];int dp[305];int main(){int W,L;while(cin>>W>>L){cin>>word;int i,j,k;for(i=0;i<W;i++)cin>>dic[i];dp[0]=0;for(i=1;i<=L;i++){dp[i]=dp[i-1]+1;for(j=0;j<W;j++) //每到一个字符，就跟字典中的单词进行匹配{int len=strlen(dic[j]);int pos=i-1;k=len-1;while(pos>=0&&k>=0) //从后向前匹配{if(word[pos]==dic[j][k])k--;pos--;}if(k<0) //说明匹配成功{int tmp=dp[pos+1]+(i-(pos+1)-len);dp[i]=dp[i]<tmp?dp[i]:tmp;}}}cout<<dp[L]<<endl;}return 0;}