学步园

题意：有一长为L的message 和W个word in the dictionary 。要求去除message中的某些字符使其由the
word of the dictionary 组成 （当然，要求是去掉最少的）

原文地址：http://blog.csdn.net/lyy289065406/article/details/6648121

思路：

dp[i]表示从message中第i个字符开始，到第L个字符（结尾处）这段区间所删除的字符数，初始化为dp[L]=0

由于我的程序是从message尾部向头部检索匹配，所以是下面的状态方程：

 

从程序可以看出，第i个位置到L所删除的字符数，总是先取最坏情况，只有可以匹配单词时才进入第二条方程进行状态优化更新。

 

第一条方程不难理解，只要弄懂dp[i]的意义就能简单推导

第二条方程难点在dp[pm]+(pm-i)-len

从程序知道，pm是message的指针（其中i表示当前所匹配的单词在message中的起始位置），pd是字典的指针

匹配的过程是：

当确认message第i位和某单词的首位吻合时，就开始逐字匹配，字符相同则两个指针同时向后移动一次，否则pd固定，pm移动。当因为pm>L跳出匹配时，说明匹配失败，dp[i]状态不变；当pd==单词长度时，单词匹配成功，进行dp[i]的状态优化

 

显然，匹配成功时，pm-i代表匹配过程中，从位置i到pm的区间长度，再减去单词长度len，则得到从i到pm所删除的字符数
(pm-i)-len。又dp[pm]表示从pm到L所删除的字符数（根据检索方向，dp[pm]的值在此前已经被作为最坏打算处理，因此并不是空值）

从而dp[pm]+(pm-i)-len表示i到L删除的字符数，不难证明这个值一定比dp[i]相等或更优，因此取min赋值给dp[i]

//344K   
79MS
#include <stdio.h>
#include <string.h>
#define M 305
int w,l;
char meg[M],word[605][M];

int min (int a,int b)
{
    return a
> b ? b : a;
}
void DP ()
{
    int
dp[M];
    int
i,j,pm,pw;
    dp[l] =
0;
    for (i =
l-1; i >= 0; i --)
    {
       
dp[i] = dp[i+1] +  1;
       
for (j = 0; j < w; j ++)
       
{
           
int len = strlen (word[j]);
           
if (word[j][0] == meg[i] && l - i
>= len)
           
{
               
pm = i;
               
pw = 0;
               
while (pm < l)
               
{
                   
if (word[j][pw] == meg[pm++])
                       
pw ++;
                   
if (pw == len)
                   
{
                       
dp[i] = min (dp[i],dp[pm] + (pm-i-len));