题目链接： 

从后往前遍历，dp[i]表示第i个字符到最后一个字符删除的字符个数。

状态转移方程为：

dp[i] = dp[i+1] + 1;                                                 //当不能匹配时

dp[i] = std::min(dp[i], dp[msg] + (msg-i) - len[j]);  //当匹配时。

第i个字符到第msg个字符之间一共有msg-i个字符，减去字典中单词的长度，就是删除的字符数量。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 int n, m, dp[610], len[610]; 5 char s[610], dic[610][30]; 6 int main() 7 { 8     while(scanf("%d %d", &n, &m) != EOF) 9     {10         scanf("%s", s);11         for(int i = 0; i < n; i++)12         {13             scanf("%s", dic[i]);14             len[i] = strlen(dic[i]);15         }16         dp[m] = 0;17         for(int i = m-1; i >= 0; i--)18         {19             dp[i] = dp[i+1] + 1;20             for(int j = 0; j < n; j++)21             {22                 if(s[i] == dic[j][0] && m-i >= len[j])23                 {24                     int msg = i+1, cnt = 1;25                     while(msg < m && dic[j][cnt])26                     {27                         if(s[msg++] == dic[j][cnt])28                             cnt++;29                     }30                     if(cnt == len[j])31                         dp[i] = std::min(dp[i], dp[msg] + (msg-i) - len[j]);32                 }33             }34         }35         printf("%d\n", dp[0]);36     }37     return 0;38 }