899. 编辑距离

题意

输入n个字符串，然后输入m个询问，每一次询问，输入一个字符串和一个限制，在限制的操作次数之内，有多少个字符串可以编辑为询问的字符串，输出这个数字

输入

3 2
abc
acd
bcd
ab 1
acbd 2

输出

1
3

数据范围

1≤n,m≤1000
字符串的长度不超过10

代码

#include<bits/stdc++.h>

using namespace std;

const int N=15,M=1010;

int dp[N][N];
char str[M][N];
int n,m;

int edit(char a[],char b[])
{
   int la=strlen(a+1),lb=strlen(b+1);
   
   for(int i=1;i<=la;i++)  dp[i][0]=i;
   for(int i=1;i<=lb;i++)  dp[0][i]=i;
   
   for(int i=1;i<=la;i++)
   {
       for(int j=1;j<=lb;j++)
       {
           dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
           dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i]!=b[j]));
       }
   }
   
   return dp[la][lb];
}

int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   
   cin>>n>>m;
   
   for(int i=1;i<=n;i++)   cin>>(str[i]+1);
   
   while(m--)
   {
       int res=0,limit;
       char s[M];
       
       cin>>(s+1)>>limit;
       
       for(int i=1;i<=n;i++)
       {
           if(edit(str[i],s)<=limit)  res++;
       }
       
       cout<<res<<endl;
   }
   
   return 0;
}

总结

属于线性dp问题

dp集合表示的是从长度是i的字符串编辑长度是j的字符串的操作次数，维护这个数值为最小操作次数

状态计算和转移

分成三种情况，删除就是一个字符串前面 i - 1 个元素和后面一个字符串前面 j 个元素一一对应相等，操作次数是 dp [ i - 1 ] [ j ] + 1 ，加一表示删除这一步操作，增加是一个字符串的前面 i 个元素和另一个字符串前面 j - 1 个元素对应相等，增加一个元素使得两个字符串完全相等，dp [ i ] [ j - 1 ] + 1 ,修改有两种情况，最后一个元素相等的话就需要直接就是 dp [ i - 1 ] [ j - 1 ]，最后一个元素不相等的话，就在 dp [ i - 1 ] [ j - 1 ] 的基础上增加一个修改操作

输入的时候下标从 1 开始使用会比较方便

因为只要涉及减一的下标，就需要注意数组越界的情况，所以不如以后所有的情况都使用1开始作为数组下标

计算数组长度的时候，比如使用strlen函数也需要把括号里面的数组加一

int la=strlen(str+1);

该题属于上一道编辑距离的简单应用

关键还是理解线性dp的含义，也就是状态计算那个部分，分类讨论，不重不漏