dp真的太考验思维的灵活程度了。。看似一个微不起眼的细节可能背后蕴含了很大的思考容量。

常想常新，每次都在推翻自己之前的认识

emmm时隔一个月，再来看又不认识了。。

emmm我也是

我又回来了，在二刷的过程中，仿佛依旧在学习新的知识，中间间断了很久。但是第一次看大致云里雾里，似懂非懂。第二次看，看之前只需要知道一个大致的概念，就能推导出朴素做法，略有进步~

你妹夫的悄悄卷哈 刚发现1月还学了

77777

有些不明白，在分成三类中，第一类删除，为什么一定是删除最后一个a[i]呢？题目中不是说了可以删除任一个元素么？如果是删除中间的元素，比如说a[0]之后变成和b[1-j]相等，这种情况还能用f[i-1][j]么

因为是逐步更新的，每个状态可由前面状态计算出，如果删除的是中间元素，那么中间元素被删除的那个状态肯定被算过了,在那个状态下”中间元素“也是以最后一个元素被计算出

举个例子， 字符串a和b分别为 “abcde” 、 “bcde”, 在初始化f[1,0] = 1的时候，a[0]已经被删除了，进而后面遍历到f[2,1] f[3,2] f[4,3] f[5,4]的时候，已不再需要进行增删替换操作

这里的意思应该是你无论怎么操作，我们始终看a的最后一位a[i]是怎么操作的，因为a[i]只有三种操作，所以划分为三类

贴个知乎上的链接吧，是从国外论文翻译总结的，看起来挺麻烦的，我也没仔细看…
编辑距离证明
你的疑惑是正确的，我看了一圈大家的理解，我觉得很多人理解都因果颠倒了…属于是强行说服了自己

谢谢分享！我也去看看怎么证明的XD 感谢

好长~

其实根本原因是，操作的顺序不影响操作的结果，先调整中间再调整最后和先调整最后，再调整中间，效果是一样的，所需要的步骤也是一样的。而我们根据最后元素来对集合进行分类操作显然更加清晰，更好得出最终的状态方程。

有点牵强

关于这个问题我写了一个题解
https://www.acwing.com/solution/content/250719/
大致思路是证明一个操作序列存在任意操作顺序的等效序列，状态表示时只考虑按顺序处理字符串的操作序列集合。希望大家可以帮我看看有没有错误，谢谢！

个人觉得LeetCode的代码好懂一些（倒是过了）
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=1+min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]);

#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    cin >> n >> a + 1 >> m >> b + 1;
    for (int i = 1; i <= n; i++) f[i][0] = i;
    for (int i = 1; i <= m; i++) f[0][i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1]; //相等取上一状态或者当前状态
            else f[i][j] = min(min(f[i - 1][j], f[i][j - 1]) + 1, f[i - 1][j - 1] + 1); //不相等看删除,修改,新增成本
        }
    cout << f[n][m];
}

你这肯定错了

可以过的

马老师肯定过的

为什么不是奥林匹斯

作词 : 无

作曲 : Haiwee

音频 : 倒悬的橘子

作曲 : Haiwee

朋友们好啊

我是混元形意太极门掌门人

马保国

刚才有个朋友问我

马老师发生甚么事了

我说怎么回事

给我发了几张截图

我一看 哦

我大意了啊

没有闪

一个偷袭

打我脸

我大意了啊

没有闪

流着眼泪

捂着眼

我大意了啊

大意了

大意了

大意了

没有闪

没有闪

没有闪

正蹬

鞭腿

刺拳

下手轻一点

我说年轻人不讲武德

英国大力士不讲武德

马老师自然是五张五合

打到他全身负伤骨折

我一看 哦

大意了啊

打了我的婷婷

这时间她笑一下

准备和我窝里斗

我一个

接！

化！

发！

她叫到

爹！

爸！

妈！

啊~

婷婷这是闪电鞭你

别！

怕！

它！

我说年轻人你不懂马家功夫别害羞

我的混元鞭法传到了伦敦 泰国 和欧洲

什么西方搏击术又什么MMA

WTF

四两拨千斤 哦

你不知道吗？

来

马家没有套路

骗！

马家只有少妇

骗！

马家劝你耗子尾汁

打到你穿尿布

我大意了啊

没有闪

一个偷袭

打我脸

我大意了啊

没有闪

流着眼泪

捂着眼

滚动歌词贡献者：独倾[HTML_REMOVED]0

刚听到这首歌，笑了

问下大佬们为什么要取最小值而不是根据i和j的情况来赋值呢 if(a[i]==b[j])
dp[i][j]=dp[i-1][j-1];
else
{
if(i<j)
dp[i][j]=dp[i][j-1]+1;
else if(i==j)
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=dp[i-1][j]+1;
}

一个样例
4
uuaz
4
ulua
a[i] != b[j] && i == j 的情况下会强制选择改这种操作，但是这并不是最好的选择，这个样例里删加增优于这种选择，所以要取最小值，得到最好的做法。

好滴 谢谢大佬

草，你跟我想几乎差不多

nb

@Shadow 此题INF不赋没有关系。
f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
。。。

 000       _______    
00000-----/  /   /
 000   ||   /__ /__

去看leetcodet题解吧,这个说的不清楚

写得好呀

增删改都要+1，不改就不用

第二个插入错了把 ，题目说只能在A上插入修改成B

退役一年多了（小声bb）我跑起来没啥问题呢

我也想问，但是跑起来其实没问题，就是不理解

a插入一个数等价于b删除一个数。

插入没有错，f[i][j]的含义是以a[1 ~ i]为起点，b[1 ~ j]为终点的变换次数，并不是说将a[1 ~ i]的每一位变成b[1 ~ j]，而是在这个条件下的转化次数，所以先将a[1 ~ i]转化成b[1 ~ j - 1]，所用的操作数为f[i][j - 1]，然后在b[1 ~ j - 1]后面添加一个b[j]，也就是加1，所以f[i][j] = f[i][j - 1] + 1

我明白了! 同志们 !
状态表示是指a[1~i]变成a[1~j]也就是说已经有了a[1~i]和b[1~j]。举个例子:a数组是AGE,b数组是AGEF,此时i=3,j=4（从1开始）怎么变呢？就是在i后面加上一个F，不加F之前不就是应该要求1~i和1~j-1相等嘛。
我们是受了i和j长度相等的影响，考虑的情况是a数组:AGF, b数组是AGE，此时i=3,j=3,再在i-1后面加上一个E，即要求1~i和1~j相等，这是不对的。你在i-1后面加上一个E，那这个序列就变成了AGEF和AGE，那么这个F怎么办呢？所以说是不对的。

使得字符串 a 的前 i 个字母 == 字符串 b 的前 j 个字母 最后一步是插入，最后插入的位置是a[i + 1]，也就是a[i + 1] == b[ j ]，所以是从f[i][j - 1]转移过来

感觉是dp+贪心

这里我有一个疑问，删除一个字母，是对于a串说的，是f[i-1,j]+1,增加一个字母是相对于a串说的，是f[i,j-1]+1,但是并没有涵盖住所有情况，但如果把f[i-1,j]的含义看作删除a曾加b,把f[i,j-1]看作删除b增加a,就涵盖住所有情况了

厉害的orz

orz

大佬们，for(register int i=1; i<=lena; i)
for(register int j=1; j<=lenb; j)
f[i][j] = INF;为什么这个用memset赋值,答案不对

找有负数的max别忘了-INF是什么意思啊，小白不太清楚，能解释一下吗

f[i][j] = Math.min(f[i-1][j],f[i][j-1]) +1; //插入或者删除
if (a[i] == b[j]) f[i][j] =Math.min(f[i][j],f[i-1][j-1]); 为什么a[i] == b[j]时，不是直接f[i][j] = f[i-1][j-1]而是也需要将 f[i][j] = Math.min(f[i-1][j],f[i][j-1]) +1; //插入或者删除 的值和f[i-1][j-1]比较，f[i-1][j-1]不是肯定比上一步花费少吗

求助
//三种处理操作 增删改
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]

using namespace std;

const int N = 1010;
const int INF = 2e9;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
memset(f, 0x3f3f3f3f, sizeof(f));

scanf("%d%s", &n, a + 1);  //因为状态转移方程会出现i - 1，懒得写越界条件直接从1开始存
scanf("%d%s", &m, b + 1);

//处理边界问题
for(int i = 0 ; i <= n ; i ++)  f[0][i] = i;  //a为空,变成b[i]的次数是i
for(int j = 0 ; j <= m ; j ++)  f[j][0] = j;  //b为空，变成a[j]的次数是j   f存的是次数 所以无论是a变成b还是b变成a都无所谓

for(int i = 1 ; i <= n ; i ++)   //a[0]和 b[0]的特殊情况处理完了，直接从a[1]b[1]开始计算就好
 for(int j = 1 ; j <= m ; j ++)
  {

      f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j] + 1);   //增删
      if(a[i] == b[j])  //i - 1和 j - 1相等才会动用这个操作，  如果a[i] == b[j].则不用+1 否则+1 
         f[i][j] = min(f[i][j], f[i - 1][j - 1]);
      else
         f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
  }

  cout << f[n][m] << endl;


return 0;

}
这代码为啥错了啊

兄弟，你这个代码其实不需要memset，因为你是先取增删中的最小值，不会出现和初始值（还没求出的dp）比较的情况，问题出在:
for(int i=1; i <= n; i) dp[i][0] = i;
for(int j=1; j <= m; j) dp[0][j] = j;

我个人理解插入操作：fij表示前i个a和前j个b可以匹配的操作方式最小值，由于插入ai＋1后与bj相同，那么在插入前a的前i个和b的前j-1个就已经匹配，所以状态转移方程应该为fi j-1 再加上一个插入操作

这个题解里插入操作解释为插入bj后相同，我感觉解释有点牵强