题意:给出一个主串，和一本字典，问最少在主串删除多少字母，可以使其匹配到字典的单词序列。
分析：从后先前推，dp[i]表示从i到mes结尾需删除的字符个数。
最坏的情况是 dp[i] = dp[i+1] + 1;
从i开始找与dic[]中的匹配，设 pm是mes[]的下标，如果出现从mes[i] 到 mes[pm] 这一段正好和dic[]里的一个串匹配，
则 dp[i] = min(dp[i], dp[pm] + pm - i - len)。 pm - i 表示这一段字串的长度，len表示dic[]里与之匹配的串的长度。pm - i - len 就是[i, pm]段需要删除的字符个数。
代码如下：
#include <iostream> #include <fstream> #include <string> #include <algorithm> using namespace std; string mes; string dic[605]; int dp[305]; int main() { //fstream cin("test.txt"); int n, mes_len; cin >> n >> mes_len; cin >> mes; for (int i = 0; i < n; i++) cin >> dic[i]; //初始化 for (int i = mes_len; i >= 0; i--) { dp[i] = mes_len - i; } for (int i = mes_len - 1; i >= 0; i--) { dp[i] = dp[i + 1] + 1; bool flag = 0; for (int j = 0; j < n; j++) //枚举字典 { int dic_len = dic[j].length(); if (dic_len <= mes_len - i&&mes[i] == dic[j][0]) //字典小于i到mes_len的长度 { //且首字母与mes[i]匹配 int pd = 0; //dic指针 int pm = i; //mes指针 while (pm < mes_len) //逐字符匹配 { if (mes[pm] == dic[j][pd]) { pd++;pm++; } else pm++; if (pd == dic_len) { dp[i] = min(dp[i], dp[pm] + pm - i - dic_len);//dp[pm]表示从pm到mes_len删除的字符数 break; //pm - i - dic_len表示从i到pm需要删除的字符数 } } } } } cout << dp[0] << endl; //system("pause"); return 0; }