链接：Luogu-1279
思路
如何实现“插入空格”操作？
定义状态为$f(i,j)$，表示字符串A中从第$i$个字符到结尾，字符串B中从第$j$个字符到结尾，所能得到的最小字串距离。显然，可以把$i,j$都前移，也就是转移到$f(i+1,j+1)$。那空格怎么处理呢？我们用$i,j$中的一个加1，另一个不变，来表示在某个字符的前面插入一个空格。 如图：
实现了插入空格，就可以书写状态转移方程了: 设$m$,$n$为字符串$A$,$B$之长度，则：
\[f(i,j)=\min \begin{cases} f(i+1,j)+k & \text{ if } i \leq m \\ f(i,j+1)+k & \text{ if } j \leq n\\ f(i+1,j+1)+|A_i-B_j| & \text{ if } i \leq m \wedge j \leq n \end{cases}\]注意：在处理序列DP类问题时，尤其是多个序列的DP问题时，一定要处理边界情况！ 要设计序列长度差别大的数据，并输出递推结果以检查。
有两个地方易错：
- 如果按照上文的状态定义，那么就一定要更新处理f[][n+1]和f[m+1][]。因为可能需要在字符串末尾补空格！
- 状态转移方程每一项的取得都有着条件！第一，二项只在$i$,$j$在长度范围内时取得，也就是说$i$达到了$m+1$，$j$达到了$n+1$之后就不能再前移（边界）；同理，第三项是把$i$,$j$都前移，必须满足$i \leq m$且$j \leq n$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define SETINF(x) memset(x,0x3f,sizeof(x))
using namespace std;
char A[2010],B[2010];
int K,m,n,opt[2010][2010];
int main(){
scanf("%s",A+1);scanf("%s",B+1);
scanf("%d",&K);
m=strlen(A+1);n=strlen(B+1);
SETINF(opt);opt[m+1][n+1]=0;
for(int i=m+1;i>=1;i--)
for(int j=n+1;j>=1;j--){
if(i<=m) opt[i][j]=min(opt[i][j],opt[i+1][j]+K);
if(j<=n) opt[i][j]=min(opt[i][j],opt[i][j+1]+K);
if(i<=m && j<=n) opt[i][j]=min(opt[i][j],opt[i+1][j+1]+abs(A[i]-B[j]));
}
printf("%d\n",opt[1][1]);
}
