动态规划--编译距离

72. 编辑距离https://leetcode.cn/problems/edit-distance/

题目速览：

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = \"horse\", word2 = \"ros\"输出：3解释：horse -> rorse (将 \'h\' 替换为 \'r\')rorse -> rose (删除 \'r\')rose -> ros (删除 \'e\')

示例 2：

输入：word1 = \"intention\", word2 = \"execution\"输出：5解释：intention -> inention (删除 \'t\')inention -> enention (将 \'i\' 替换为 \'e\')enention -> exention (将 \'n\' 替换为 \'x\')exention -> exection (将 \'n\' 替换为 \'c\')exection -> execution (插入 \'u\')

分析过程：

1.状态表示：

        定义 dp[i][j] 表示将s1的前i个字符转换为s2的前j个字符所需的最少操作次数。

2.状态转移方程：

        当s1[i]==s2[j]时，字符相同，不需要操作，此时dp[i][j]=dp[i-1][j-1]；

        当s1[i]不等于s2[j]时，此时要考虑三种操作·：

                1.删除：dp[i][j]=dp[i-1][j]+1，删去s1字符串的第i个字符；

                2.插入：dp[i][j]=dp[i][j-1]+1，将s2的的第j个字符到s1；

                3.替换：dp[i][j]=dp[i-1][j-1] + (s1[i-1] == s2[j-1] ? 0 : 1)

        然后取这三种情况的最小值：

dp[i][j] = min(
    dp[i-1][j] + 1,     // 删除
    dp[i][j-1] + 1,     // 插入
    dp[i-1][j-1] + (s1[i-1] == s2[j-1] ? 0 : 1)  // 替换或不变
);

3.初始化

  dp[0][j] = j：将空字符串转换为word2的前j个字符，需要j次插入

  dp[i][0] = i：将word1的前i个字符转换为空字符串，需要i次删除

代码示例:

class Solution {public: int minDistance(string s1, string s2) { int m=s1.size(),n=s2.size(); vector<vector> dp(m+1,vector(n+1)); for(int i=0;i<=m;i++) dp[i][0]=i; for(int j=0;j<=n;j++) dp[0][j]=j; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]; else{  dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1}); } } } return dp[m][n]; }};

        这个算法是解决编辑距离问题的标准方法，在很多实际应用中都有使用，比如拼写检查、DNA序列比对等。