下面是作业题目和力扣上的问题

动态规划算法，比较困难，这里附上一个比较容易懂的视频链接

https://www.youtube.com/watch?v=MiqoA-yF-0M

这是算法的伪代码

下面我们拿Sundays和Saturday为例，做一个动态规划表

	“”	s	u	n	d	a	y	s
“”	0	1	2	3	4	5	6	7
s	1	0	1	2	3	4	5	6
a	2	1	1	2	3	3	4	5
t	3	2	2	2	3	4	4	5
u	4	3	2	3	3	4	5	5
r	5	4	3	3	4	4	5	6
d	6	5	4	4	3	4	5	6
a	7	6	5	5	4	3	4	5
y	8	7	6	6	5	4	3	4

我们看到了最后的交点就是4

这里我贴上花花酱的链接和他的答案

https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-72-edit-distance/

#include<bits/stdc++.h>
using namespace std;
int minDistance(string word1, string word2) {
    int l1 = word1.length();
    int l2 = word2.length();
    // d[i][j] := minDistance(word1[0:i - 1], word2[0:j - 1]);
    //这是个建表操作建立l1+1列，每一列填充vector<int>(l2+1,0)这个数组
    //也就是（l2+1）个0，也就是l2+1行
    vector<vector<int>> d(l1 + 1, vector<int>(l2 + 1, 0));

    //然后给第一行第一列都标上行数列数
    for (int i = 0; i <= l1; ++i)
        d[i][0] = i;
    for (int j = 0; j <= l2; ++j)
        d[0][j] = j;
	//开始动态规划
    for (int i = 1; i <= l1; ++i)
        for (int j = 1; j <= l2; ++j) 
        {
//这个就是delta如果这两个字符串最后一个数字相等，那么delta=0，否则delta=1
            int delta = (word1[i - 1] == word2[j - 1]) ? 0 : 1;
// 这就是最核心的算法           
 d[i][j] = min(d[i - 1][j - 1] + delta,min(d[i][j - 1], d[i - 1][j]) + 1);
		}
    for(int i =0;i<=l1;i++)
    {
        for(int j =0;j<=l2;j++)
        {
            printf("%3d",d[i][j]);
        }
        cout<<endl;
    }
    return d[l1][l2];
}
int main()
{
	string word1,word2;
	cin>>word1>>word2;
	cout<<minDistance(word1,word2)<<endl;
	return 0;
}

72Edit_Problem

下面是作业题目和力扣上的问题

结果如下