The Cow Lexicon POJ - 3267 dp
题意 给出一个母串 和一个字典 问母串最少删去几个字母 删去后的母串是由字典里面的单词拼起来的
思路：dp[i]表示从i到母串结尾最少需要删除多少个字母 初始化dp[length]=0 最坏情况dp[i]=dp[i+1]+1
状态转移方程 dp[i]=min(dp[i],dp[p]+p-len-i) p 匹配单词的最后一个位置 len是字典里面单词的长度 i是开始匹配的位置 p-len-i的意义就是匹配过程中删除了多少个字母
参考：http://www.cnblogs.com/lyy289065406/archive/2011/07/31/2122638.html
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 char s[305]; 6 char dir[605][305]; 7 int dp[1000]; 8 int main(){ 9 int w,l; 10 scanf("%d%d",&w,&l); 11 scanf("%s",s); 12 for(int i=0;i<w;i++){ 13 scanf("%s",dir[i]); 14 } 15 dp[l]=0; 16 for(int i=l-1;i>=0;i--){ 17 dp[i]=dp[i+1]+1; 18 for(int j=0;j<w;j++){ 19 int len=strlen(dir[j]); 20 int pm=0; 21 if(l-i+1>=len&&s[i]==dir[j][0]){ 22 int p2=i; 23 while(p2<l){ 24 if(dir[j][pm]==s[p2++]){ 25 pm++; 26 } 27 if(pm==len){ 28 dp[i]=min(dp[i],dp[p2]+p2-i-len); 29 break; 30 } 31 } 32 } 33 } 34 } 35 cout<<dp[0]<<endl; 36 return 0; 37 }
