最少编辑次数 · 300 · 公开题解

思路

以两个前缀为状态，枚举最后一步是插入、删除还是替换。

复杂度

$O(|A||B|)$ 时间与空间。

易错点

• 认真处理最小规模、重复值、不可达或全负数等边界。
• 需要累加的题目优先使用 64 位整数。
• 不要根据样例特判；隐藏数据包含随机、边界与退化结构。

C++17 参考实现

#include <bits/stdc++.h>
using namespace std;
int main(){string a,b;cin>>a>>b;vector<vector<int>>d(a.size()+1,vector<int>(b.size()+1));for(int i=0;i<=a.size();i++)d[i][0]=i;for(int j=0;j<=b.size();j++)d[0][j]=j;for(int i=1;i<=a.size();i++)for(int j=1;j<=b.size();j++)d[i][j]=a[i-1]==b[j-1]?d[i-1][j-1]:1+min({d[i-1][j],d[i][j-1],d[i-1][j-1]});cout<<d[a.size()][b.size()]<<'\n';}

来源与授权

• 题目与数据： 智链细米 IT 社区原创训练变体（edit-distance-0244）。
• 知识路线参考： AlgoNote @ 2aa4fd0a2214；代码随想录 @ b43def349578。
• 引用说明： 代码随想录作者为程序员 Carl；本题没有复制 LeetCode 或第三方竞赛题面、样例、题解与测试数据。
• 授权记录： organizer-confirmed-2026-08-07。
• 主办方： 智链细米 IT 社区；设备支持： EaglesLab。