问题
给定你一个字符串，和n个单词构成的字典。让你求出在字符串中最小删去几个字母，使得剩下的字符串能够由字典中的若干个单词构成。输出最少删去的字母的个数。
分析
考虑给定字符串中第i个字符，可能删去，可能保留。——定义划分状态的关键。
d[i]=Min{d[i-1]+1,make(i)}//delete vs not delete
如果不删去，则它一定是作为某个单词的末尾。故与该位置前的状态有关系。make(i)中，要比较，所有字典中以msg[i]结尾的单词：若要保留，则此过程中删去字母个数ct,return 就是Min{d[该单词首字母的前一个字符位置]+ct}
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define INF 1000000
#define MIN(a,b) (a)>(b)?(b):(a)
int N,L;
char dic[600][26],msg[305];
int f[305];//记录第i位前丢弃的最少字母数
int make(int m)
{
int k,j,ct=0,n=m,t,re=INF;
for(k=0;k<N;++k)
{
if(dic[k][strlen(dic[k])-1]==msg[m])//若写m为n此处n=0,WA
{
n=m;ct=0;
j=strlen(dic[k])-1;
while(j>=0)
{
while(n>=0&&msg[n]!=dic[k][j])
{
n--;
ct++;
}
if(n>=0&&msg[n]==dic[k][j])n--;//当n小于0时说明此单词比该msgd第n位前的字串长
else break;
j--;
}
//if(j==-1&&ct+f[n-1]<re)
//{
// re=ct+f[n-1];
// //t=n;
//}
if(j==-1)//说明字典中存在以msg【n】结尾的子串=该单词
{
if(n>=0&&ct+f[n]<re)//由于上一个if语句多减了一次1，所以此时perhaps n<0
re=ct+f[n];
else if(n<0&&ct<re)re=ct;//此时说明msg中的该单词恰好是从msg[0]开始的
}
}
}
/**//*if(re==INF)头开始误导了，想着总是加一，不对。其实是对的，会自己判断选择到达该状态的其他路径，
return f[m-1]==0?0:f[m-1]+1; 故此处多余*/
return re;
}
int main()
{
int len,i,j,k;
scanf("%d",&N);
scanf("%d",&len);
scanf("%s",msg);
//for(i=0;i<len;i++)调试时的代码一定要记得注释掉！！！WA两次因此。太suck了
// printf("%c ",msg[i]);
//printf("\n");
//for(i=0;i<len;i++)
// printf("%-2d",i);
//printf("\n");
for(i=0;i<N;++i)
{
scanf("%s",dic[i]);
}
len=strlen(msg);
f[0]=1;//初始状态可能不为1，即第一个字符也可能作为字典单词的最后一个字母，此时该单词位单字母单词
for(i=0;i<N;++i)
if(strlen(dic[i])==1&&dic[i][0]==msg[0])f[0]=0;
for(i=1;i<len;i++)
{
f[i]=MIN(f[i-1]+1,make(i));
}
printf("%d\n",f[len-1]);
}