题意

给两个字符串，求最小编辑次数让两个字符串相等。

其中编辑允许的操作

1. 增加一个字符
2. 修改一个字符
3. 删除一个字符

限制：每个字符串长度小于500

方法

动态规划

考虑设计状态 dp[i][j] 表示，第一个字符串s匹配了i个字符，第二个字符串t匹配了j个字符的最小编辑代价

那么有转移方程

dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1, dp[i-1][j-1]+ s[i] != t[i])

分别表示，删除s第i个字符，删除第j个字符，s[i]和t[j]配对的代价。

以样例

abcde
abcdf

为例

我们最后 dp[len(s)][len(t)]便是要求的答案

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

char s[510];
char t[510];

int main(){
    
    while(~scanf("%s",s)){
        scanf("%s",t);
        int ns = strlen(s);
        int nt = strlen(t);
        vector<vector<int> > dp(ns+1,vector<int>(nt+1,0x3f3f3f3f));
        rep(i,0,ns+1){
            rep(j,0,nt+1){
                if(i*j == 0){
                    dp[i][j] = i+j;
                    continue;
                }
                dp[i][j] = dp[i-1][j-1] + (s[i-1] != t[j-1]);
                dp[i][j] = min(dp[i][j],dp[i-1][j]+1);
                dp[i][j] = min(dp[i][j],dp[i][j-1]+1);
            }
        }
        printf("%d\n",dp[ns][nt]);
    }
    return 0;
}

复杂度分析

时间复杂度: 除了字符串读入是$O(\mathrm{\mid }s\mathrm{\mid }+\mathrm{\mid }t\mathrm{\mid })O(|s|+|t|)$，剩下的是状态数组建立和计算，每个位置被计算一次，状态转移是常数代价，所以总时间复杂度为$O(\mathrm{\mid }s\mathrm{\mid }\cdot \mathrm{\mid }t\mathrm{\mid })O(|s|\backslash cdot\; |t|)$

空间复杂度: 空间一部分是字符串读入$O(\mathrm{\mid }s\mathrm{\mid }+\mathrm{\mid }t\mathrm{\mid })O(|s|+|t|)$，另一个部分是状态$O(\mathrm{\mid }s\mathrm{\mid }\cdot \mathrm{\mid }t\mathrm{\mid })O(|s|\backslash cdot\; |t|)$，所以总空间复杂度为$O(\mathrm{\mid }s\mathrm{\mid }\cdot \mathrm{\mid }t\mathrm{\mid })O(|s|\backslash cdot\; |t|)$

递推

设计状态dp[i][j]表示字符串s的第i个字符和字符串t的第j个字符匹配的最小次数

考虑状态转移

也就是找到上一个匹配的字符的位置s[i0][j0]，然后中间两段字符全部改写,代价$max(i-i_0-1,j-j_0-1)max(i-i\_0-1,j-j\_0-1)$,在加上当前位置匹配

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

char s[510];
char t[510];

int main(){
    
    while(~scanf("%s",s)){
        scanf("%s",t);
        int ns = strlen(s);
        int nt = strlen(t);
        vector<vector<int> > dp(ns+2,vector<int>(nt+2,0x3f3f3f3f));
        rep(i,0,ns+2){ // s位置i
            rep(j,0,nt+2){ // 和t位置j对应
                if(i*j == 0){
                    dp[i][j] = i+j;
                    continue;
                }
                int cost = 0x3f3f3f3f;
                rep(ii,0,i){
                    rep(jj,0,j){
                        cost = min(cost,dp[ii][jj]+max(i-ii-1,j-jj-1));
                    }
                }
                dp[i][j] = cost + (s[i-1] != t[j-1]);
            }
        }
        printf("%d\n",dp[ns+1][nt+1]);
    }
    return 0;
}

复杂度分析

时间复杂度: 最深的搜索每次转移的上一个位置，复杂度达到了$O(\mathrm{\mid }s{\mathrm{\mid }}^2\cdot \mathrm{\mid }t{\mathrm{\mid }}^2)O(|s|^2\backslash cdot\; |t|^2)$ 然而它神奇的过了

空间复杂度: 主要是设计的状态$O(\mathrm{\mid }s\mathrm{\mid }\cdot \mathrm{\mid }t\mathrm{\mid })O(|s|\backslash cdot\; |t|)$