给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
思路一：动态规划
int minDistance(char * word1, char * word2){
//动态规划
int dp[501][501];
int i,j;
int size1=strlen(word1);
int size2=strlen(word2);
dp[0][0]=0;
for(i=0;i<=size2;i++){
dp[0][i]=i;
}
for(i=0;i<=size1;i++){
dp[i][0]=i;
}
for(i=1;i<=size1;i++){
for(j=1;j<=size2;j++){
dp[i][j]=fmin(dp[i-1][j],fmin(dp[i][j-1],dp[i-1][j-1]))+1;
if(word1[i-1]==word2[j-1]){
dp[i][j]=fmin(dp[i][j],dp[i-1][j-1]);
}
}
}
return dp[size1][size2];
}时间复杂度O(n^2)，空间复杂度O(n)
分析：
本题将一个字符串变为另一个字符串，首先长度需变为一致，即删除一个或者插入一个，再将两个字符串中字符变为相同，删除和插入的操作可转化为 dp[i][j]=fmin(dp[i-1][j],fmin(dp[i][j-1],dp[i-1][j-1]))+1;，替换的操作转化为dp[i][j]=fmin(dp[i][j],dp[i-1][j-1]);最后输出dp[size1][size2]文章来源：https://www.toymoban.com/news/detail-643848.html
总结：
本题考察动态规划问题，将删除，插入，替换的操作转换为动态规划内比较两个格子值大小即可解决文章来源地址https://www.toymoban.com/news/detail-643848.html
到了这里，关于leetcode做题笔记72的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[做题]动态规划](https://imgs.yssmx.com/Uploads/2024/04/855930-1.jpeg)
