Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters 'a'..'z'. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.
The cows want you to help them decipher a received message (also containing only characters in the range 'a'..'z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.
開始的時候覺得很難，后來仔細思考之后才發現切入點，重要的還是看出一個合適的子問題，總之DP題目就得多練才能出眼光。
設dp[i]為前i個字符轉為合法所需刪除的字母個數，那么當我們遞推dp[i+1]的時候，實際上就是嘗試尋找一個字典里的串，它也以sourc[i+1]收尾(有的做法是以i字母打頭往前推)，那么這時候dp[i+1]需要知道的就是 dp[i-(cnt+w[j])]處的結果，cnt+w[j]是倒退的長度，這個長度包含了某個合法串長度w[j]和cnt個被刪除的字符，此時推得一個臨時解，所有字典單詞推出的臨時解中最小的一個轉移之。
轉移方程：DP[i]=Min{ DP[i] ,DP[i-(cnt+w[k])]+cnt ,DP[i-1]+1 }
1
#include<iostream>
2#include<cstring>
3using namespace std;
4#define MIN(a,b) (a<b)?a:b
5#define L 301
6#define W 601
7int dp[L];
8int lenArr[W];
9char sourc[L+1];
10char dic[W][27];
11
int main()
{
12
int i,j,k;
13 int l,w;
14 int souPoi,dicPoi,cnt;
15
while(cin>>w>>l){
16 cin>>sourc;
17 for(i=0;i<w;i++){ cin>>dic[i]; lenArr[i]=strlen(dic[i])-1; }
18
19 for(i=0;i<=l;i++) dp[i]=0x7fffffff;
20 dp[0]=0;
21 for(i=1;i<=l;i++){
22 for(j=0;j<w;j++){
23 dicPoi=lenArr[j];
24 souPoi=i-1;
25 cnt=0;
26 /**//* 倒退匹配，若當前不匹配，則嘗試刪去一個字符 */
27 while( souPoi>-1 && dicPoi>-1 ){
28 if( sourc[souPoi] == dic[j][dicPoi] ){ --souPoi; --dicPoi; }
29 else{ ++cnt; --souPoi; }
30
}
31 if( dicPoi<0 ){ dp[i]=MIN(dp[i],dp[i-(cnt+lenArr[j]+1)]+cnt); }
32 else{ dp[i]=MIN(dp[i],dp[i-1]+1); } /**//* 匹配失敗 */
33 }
34 }
35
36 printf("%d\n",dp[l]);
37 }
38 return 0;
39
}