# POJ 3267 奶牛的字典
[POJ-3267](http://poj.org/problem?id=3267)
## 题目分析
这道题让我们从一个杂乱的字符串中, 找到仅剩已知词典包含的词汇时, 需要删除的最少字符数. 很明显, 一旦字符串的第i个字符出现, 前i个字符中需要删除的最少字符数就是确定的, 符合动态规划的特性.
因此得出如下思路:
1. 对字符串中的每一个字符, 在保留和不保留两个选项中选择要删除的字符数较少的选项, 并记录删除的字符数.
2. 以此方式遍历字符串中的所有字符后, 最后一项记录即是答案.
因此问题转变为了求保留该字符时需要删除的字符数(极限情况为是否可以保留). 貌似没有什么特殊的方法, 但有一点值得注意: 该字符必须是一个词典词汇的末尾字符, 并且该词汇中的所有字符必须在从该字符开始逆向遍历字符串的过程中依次出现.
现在思路进一步明确, 我们需要假设该字符可能为任何一个以它为末尾字符的词典词汇的末尾字符, 计算后获取到各个假设成立情况下的删除字符数的最小值(即保留该字符时的最优解). 别忘了还有之前讨论的不保留选项. 在保留和不保留(删除字符数+1)之间取得一个最小值, 就是当前字符的最优解了.
## 弯路
原来还想判断当前字��作为词典词汇中间字符的情况, 后来发现是没有必要并且不可行的:
1. 若当前字符在字符串的中间, 则没有必要判断. 因为按照题意分析, 其一定属于一个完整的单词. 只要到达词汇末尾字符后再开始搜索, 词汇中间字符的结果就会全部重现.
2. 若当前字符在字符串的尾部, 这种想法就会产生错误, 不能形成一个完整的单词.
## 转移方程
$$
\begin{align}
&&dp[i] &= 0, &i = 0 \\
&&dp[i] &= min(match(i, t), dp[i-1] + 1), &1 \le i \le 字符串长度, t \in 词典
\end{align}
$$
综上所述, 得出代码:
## 代码(C++)
```c++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> dic;
int main(){
ios::sync_with_stdio(false);
int n, m, *dp;
string str;
cin >> n >> m;
cin >> str;
dp = new int[m+1];
for(int i = 0; i < n; i++){
string tstr;
cin >> tstr;
dic.push_back(tstr);
}
dp[0] = 0;
for(int i = 1; i <= m; i++){
dp[i] = dp[i-1] + 1;
// 匹配
for(int t = 0; t < dic.size(); t++){
string word = dic[t];
int j = i - 1; // 这里-1是因为dp从1开始
int k = word.size() - 1;
int cnt = 0;
if(str[j] != word[k]) // 当前字符不是这个词的词尾
continue;
while(j >= 0 && k >= 0){
if(str[j] != word[k]){
cnt++;
}else{
k--;
}
j--;
}
if(k < 0){ // 匹配成功一例
dp[i] = min(dp[i], dp[j+1] + cnt);
}
}
}
cout << dp[m] << endl;
return 0;
}
```
![]()