状态转移算是比较好推把，但是匹配字符串很容易会超时，跟以前某个题目的用法很类似，从第i个字母往后找假如到第j个字母匹配了一个单词,这样dp[j] = dp[i-1]+j-i-l[k]+1，取小即可。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 int dp[501]; 8 char str[601][31],s1[601],l[601]; 9 int num,n,len;10 int main()11 {12 int i,j,k,u;13 scanf("%d%d",&n,&len);14 scanf("%s",s1);15 for(i = 1; i <= n; i ++)16 {17 scanf("%s",str[i]);18 l[i] = strlen(str[i]);19 }20 for(i = 0; i <= len-1; i ++)21 {22 dp[i] = i+1;23 }24 for(i = 0; i <= len-1; i ++)25 {26 for(j = 1; j <= n; j ++)27 {28 if(s1[i] == str[j][0])29 {30 num = 1;31 if(l[j] == 1)32 {33 dp[i] = min(dp[i],dp[i-1]);34 for(u = i+1;u <= len-1;u ++)35 {36 if(i-1 >= 0)37 dp[u] = min(dp[u],dp[i-1]+u-i-l[j]+1);38 else39 dp[u] = min(dp[u],u-i-l[j]+1);40 }41 }42 else43 {44 for(k = i+1; k <= len-1; k ++)45 {46 if(str[j][num] == s1[k])47 {48 num ++;49 }50 if(num == l[j])51 {52 for(u = k;u <= len-1;u ++)53 {54 if(i-1 >= 0)55 dp[u] = min(dp[u],dp[i-1]+u-i-l[j]+1);56 else57 dp[u] = min(dp[u],u-i-l[j]+1);58 }59 break;60 }61 }62 }63 }64 }65 }66 printf("%d\n",dp[len-1]);67 return 0;68 }