网站编辑工作内容怎么写,易语言 做网站mysql,wordpress关闭评论窗口,建设银行官网app动态规划
思路#xff1a; 假设 dp[i][j] 是 word1 前 i 个字母到 word2 前 j 个字母的编辑距离#xff1b;那么状态 dp[i][j] 状态的上一个状态有#xff1a; dp[i - 1][j]#xff0c;word1 前 i - 1 个字母到 word2 前 j 个字母的编辑距离#xff0c;此状态再插入一个字…动态规划
思路 假设 dp[i][j] 是 word1 前 i 个字母到 word2 前 j 个字母的编辑距离那么状态 dp[i][j] 状态的上一个状态有 dp[i - 1][j]word1 前 i - 1 个字母到 word2 前 j 个字母的编辑距离此状态再插入一个字母就迁移到 dp[i][j] 状态同理在 dp[i][j - 1] 状态 word2 插入一个字母就迁移到 dp[i][j]状态 dp[i - 1][j - 1]如果 word1 和 word2 最后一个字母相同则不需要替换否则需要进行替换增加一次编辑dp[i][j] 是这个上一状态迁移所需距离最小的值同时当一个字母为空串时需要编辑的距离为另外一个字母的长度 dp[0][j] jdp[i][0] i
class Solution {
public:int minDistance(string word1, string word2) {int sz1 word1.size();int sz2 word2.size();if (sz1 0) {return sz2;}if (sz2 0) {return sz1;}std::vectorstd::vectorint dp(sz1 1, std::vectorint(sz2 1));// if word2 emptyfor (int i 0; i sz1; i) {dp[i][0] i;}// if word1 emptyfor (int j 0; j sz2; j) {dp[0][j] j;}for (int i 1; i sz1; i) {for (int j 1; j sz2; j) {int dp_add dp[i - 1][j] 1;int dp_del dp[i][j - 1] 1;int dp_re dp[i - 1][j - 1];if (word1[i - 1] ! word2[j - 1]) {dp_re 1;}dp[i][j] std::min(std::min(dp_add, dp_del), dp_re);}}return dp[sz1][sz2];}
};
