The Cow Lexicon(dp)

http://poj.org/problem?id=3267

题意：给出一个主串，一些单词，匹配这些单词，问至少要删除多少字符。

#include <iostream>
#include <cstdio>
#include <math.h>
#include <cstring>
#include <string>
int dp[350];//dp[i]表示i->L删除的字符数
using namespace std;
int main()
{
    int n,L;
    string word[606],s;
    cin>>n>>L;
    cin>>s;
    for (int i = 0; i < n; i ++)
        cin>>word[i];
    dp[L] = 0;
    for (int i = L-1; i >= 0; --i)
    {
        dp[i] = dp[i+1]+1;//单词序列在主串中不匹配的情况
        for (int k = 0; k < n; k ++)
        {
            int len = word[k].length();
            if (len <=L-i && word[k][0]==s[i])//单词长度小于等于匹配长度并且与单词的第一个字母相同
            {
                int ps = i;//指示主串的指针
                int pw = 0;//指示单词指针
                while(ps < L)
                {
                    if (word[k][pw]==s[ps])//如果匹配相同，主串指针和单词指针都移动
                        ++pw;
                    ++ps;//如果匹配不相同，只是主串指针移动
                    if (pw >= len)//单词匹配成功，更新
                    {
                        dp[i] = min(dp[i],dp[ps]+(ps-i)-len);//ps-i-len表示从i->ps要删除的字符数
                                                             //dp[ps]表示从ps->L要删除的字符数，两者相加便是
                                                             //从i->L要删除的字符数，这个值一定<=dp[i]
                    }
                }
            }

        }
    }
    cout<<dp[0]<<endl;
    return 0;
}