鹤岗商城网站建设,wordpress数据库加速,合肥企业网站建设专家,石家庄优化题目描述 原题链接#xff1a;72. 编辑距离
解题思路
动态规划五步曲#xff1a;
#xff08;1#xff09;dp[i][j]含义#xff1a; 以word1[i - 1]和word2[j - 1]结尾子串#xff0c;经过最少次增删改后#xff0c;可让word1变为word2的步数。dp中的i对应word1中的i…题目描述 原题链接72. 编辑距离
解题思路
动态规划五步曲
1dp[i][j]含义 以word1[i - 1]和word2[j - 1]结尾子串经过最少次增删改后可让word1变为word2的步数。dp中的i对应word1中的i-1dp中的j对应word2中的j-1。
2递推公式 word1[i-1]word2[j-1]时dp[i][j] dp[i - 1][j - 1]直接由上一步转移过来。不相等时可能会进行三种操作
增dp[i][j - 1]要保持word1中0~i-1和word2中0~j-2相等后再在word1的后面加上一个数使其和word2中的j-1相等也就是dp[i][j - 1] 1加上一步增加操作。删dp[i - 1][j]要保持word1中0~i-2和word2中0~j-1相等后让word1中第i个位置的元素删除也就是dp[i - 1][j] 1加上一步删除操作。改dp[i - 1][j - 1]要保持word1中0~i-2和word2中0~j-2相等后再将word1的i-1处的元素改变使其和word2的j-1处元素相等也就是dp[i - 1][j - 1] 1加上一个改变操作。
3dp数组初始化 dp[i][0] dp[0][i] i另一方为0时需要删除i次或修改i次。
4遍历顺序 从左到右从上到下。
5举例
class Solution {
public:int minDistance(string word1, string word2) {int n word1.size(), m word2.size();vectorvectorint dp(n 1, vectorint(m 1));for(int i 0; i n; i) dp[i][0] i;for(int i 0; i m; i) dp[0][i] i;for(int i 1; i n; i) {for(int j 1; j m; j) {if(word1[i - 1] word2[j - 1]) {dp[i][j] dp[i - 1][j - 1];} else {// 不相等时进行时取增、删、改中最少的步数dp[i][j] min(min(dp[i - 1][j] 1, dp[i][j - 1] 1), dp[i - 1][j - 1] 1);}}}return dp[n][m];}
};参考文章72. 编辑距离
