赣州网站建设价格,作it去外包公司好吗,免费舆情网站直接打开,兰州网站建设推荐q479185700上墙题目链接
记忆化搜索#xff1a; 解题关键#xff1a;每次仅考虑两字符串word1、word2分别从0 - i修改成0-j下标的完全匹配(下标表示#xff09; 临界条件#xff1a;当 i 或 j 小于0时#xff0c;表示该字符串为空#xff0c;编辑距离确定为 y1 或 x1
int dp[501][501…题目链接
记忆化搜索 解题关键每次仅考虑两字符串word1、word2分别从0 - i修改成0-j下标的完全匹配(下标表示 临界条件当 i 或 j 小于0时表示该字符串为空编辑距离确定为 y1 或 x1
int dp[501][501]{0};
class Solution {
public:int minDistance(string word1, string word2) {int mword1.size(),nword2.size();for(int i0;im;i)for(int j0;jn;j)dp[i][j]INT_MAX;return dfs(m-1,n-1,word1,word2);}int dfs(int x,int y,string word1,string word2){if(x0)return y1;if(y0)return x1;if(dp[x][y]!INT_MAX)return dp[x][y];if(word1[x]word2[y])return dfs(x-1,y-1,word1,word2);int ans min(min(dfs(x-1,y,word1,word2),dfs(x,y-1,word1,word2)),dfs(x-1,y-1,word1,word2))1;dp[x][y]ans;return ans;}
};动态规划区间dp 由状态转移方程直接推得,自底向上 转移方程dp[i][j] dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] 1 此处 i / j 表示剩余待匹配长度
class Solution {
public:int minDistance(string word1, string word2) {int n word1.size();int m word2.size();//dp[i][j] dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] 1vectorvectorintdp(n1, vectorint(m1, INT_MAX));//dp[i][0] i and dp[0][j] jfor(int i0;in;i){dp[i][0] i;}for(int j0;jm;j){dp[0][j] j;}for(int i1;in;i){for(int j1;jm;j){if(word1[i-1]word2[j-1]){dp[i][j] dp[i-1][j-1];}else{dp[i][j] min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) 1;}}}return dp[n][m];}
};
