POJ 3267 The Cow Lexicon 简单DP
题目链接： http://poj.org/problem?id=3267
从后往前遍历，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 <stdio.h> 2 #include <string.h> 3 #include <algorithm> 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 ", dp[0]); 36 } 37 return 0; 38 }