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.
開始的時(shí)候覺得很難，后來仔細(xì)思考之后才發(fā)現(xiàn)切入點(diǎn)，重要的還是看出一個(gè)合適的子問題，總之DP題目就得多練才能出眼光。
設(shè)dp[i]為前i個(gè)字符轉(zhuǎn)為合法所需刪除的字母個(gè)數(shù)，那么當(dāng)我們遞推dp[i+1]的時(shí)候，實(shí)際上就是嘗試尋找一個(gè)字典里的串，它也以sourc[i+1]收尾(有的做法是以i字母打頭往前推)，那么這時(shí)候dp[i+1]需要知道的就是 dp[i-(cnt+w[j])]處的結(jié)果，cnt+w[j]是倒退的長度，這個(gè)長度包含了某個(gè)合法串長度w[j]和cnt個(gè)被刪除的字符，此時(shí)推得一個(gè)臨時(shí)解，所有字典單詞推出的臨時(shí)解中最小的一個(gè)轉(zhuǎn)移之。
轉(zhuǎn)移方程：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 /**//* 倒退匹配，若當(dāng)前不匹配，則嘗試刪去一個(gè)字符 */
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
}