企业网站软件如何用google搜索产品关键词

企业网站软件,如何用google搜索产品关键词,wordpress 文章数据表,wordpress文章显缩络图一、动态规划解编辑距离的核心原理编辑距离#xff08;Levenshtein 距离#xff09;的动态规划解法核心是用二维数组存储子问题的解#xff0c;避免递归的重复计算#xff0c;其核心逻辑基于#xff1a;定义dp[i][j]#xff1a;表示将word1的前i个字符转换成word2的前j个…一、动态规划解编辑距离的核心原理编辑距离Levenshtein 距离的动态规划解法核心是用二维数组存储子问题的解避免递归的重复计算其核心逻辑基于定义dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作次数。边界条件dp[i][0] i把word1前i个字符转成空字符串需要删除i次dp[0][j] j把空字符串转成word2前j个字符需要插入j次。状态转移如果word1[i-1] word2[j-1]当前字符相等无需操作dp[i][j] dp[i-1][j-1]如果word1[i-1] ! word2[j-1]当前字符不等取「删除、插入、替换」三种操作的最小值 1即dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1。二、动态规划解法代码逐行解析下面针对dpEditDistance函数逐行拆解帮你理解每一步的作用int dpEditDistance(string word1, string word2) { // 1. 获取两个字符串的长度mword1长度nword2长度 int m word1.size(), n word2.size(); // 2. 定义DP表静态二维数组大小(MAX_LEN1)x(MAX_LEN1) // 为什么1因为dp[i][j]对应前i/j个字符需要包含i0/j0的边界情况 int dp[MAX_LEN 1][MAX_LEN 1]; // 3. 初始化边界条件核心 // 边界1word2为空word1前i个字符转空需要删除i次 for (int i 0; i m; i) dp[i][0] i; // 边界2word1为空空字符串转word2前j个字符需要插入j次 for (int j 0; j n; j) dp[0][j] j; // 4. 填充DP表核心状态转移 // 遍历word1的每个字符i从1到m对应前i个字符 for (int i 1; i m; i) { // 遍历word2的每个字符j从1到n对应前j个字符 for (int j 1; j n; j) { // 情况1当前字符相等word1[i-1]是第i个字符因为数组从0开始 if (word1[i - 1] word2[j - 1]) { // 无需操作直接继承前i-1和j-1的结果 dp[i][j] dp[i - 1][j - 1]; } else { // 情况2当前字符不等取三种操作的最小值1 // dp[i-1][j]删除word1第i个字符操作数1 // dp[i][j-1]给word1插入word2第j个字符操作数1 // dp[i-1][j-1]替换word1第i个字符为word2第j个字符操作数1 dp[i][j] min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1; } } } // 5. 返回最终结果word1全量转word2全量的最少操作次数 return dp[m][n]; }三、实际执行示例以 horse→ros 为例我们用代码中的测试用例word1horsem5、word2rosn3看 DP 表的填充过程步骤 1初始化边界i\j0 (空)1 (r)2 (ro)3 (ros)001231122334455步骤 2填充 DP 表关键节点i1 (h)、j1 (r)h≠r→min(dp[0][1], dp[1][0], dp[0][0])1 min(1,1,0)11→dp[1][1]1i3 (r)、j1 (r)rr→dp[3][1] dp[2][0] 2i5 (e)、j3 (s)e≠s→min(dp[4][3], dp[5][2], dp[4][2])1→ 最终dp[5][3]3和代码输出一致。最终结果dp[5][3]3表示 horse 转 ros 最少需要 3 次操作删除 h、删除 e、替换 s→e或其他等价操作。四、动态规划解法的优化点可选你提供的代码用了静态二维数组虽然简单但有优化空间适合新手进阶空间优化一维数组观察状态转移可知dp[i][j]只依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]因此可以用一维数组代替二维数组空间复杂度从O(m∗n)降到O(min(m,n))int dpEditDistanceOpt(string word1, string word2) { int m word1.size(), n word2.size(); // 用一维数组长度为较短字符串1 if (m n) return dpEditDistanceOpt(word2, word1); int dp[n 1]; // 初始化边界 for (int j 0; j n; j) dp[j] j; // 填充一维DP for (int i 1; i m; i) { int prev dp[0]; // 保存dp[i-1][j-1]的值 dp[0] i; // 对应dp[i][0] i for (int j 1; j n; j) { int temp dp[j]; // 保存当前dp[j]即dp[i-1][j] if (word1[i-1] word2[j-1]) { dp[j] prev; } else { dp[j] min(min(dp[j], dp[j-1]), prev) 1; } prev temp; // 更新prev为下一轮的dp[i-1][j-1] } } return dp[n]; }总结动态规划解法的核心要点dp[i][j]定义为「word1 前 i 个字符转 word2 前 j 个字符的最少操作数」是整个解法的基础边界条件处理空字符串的特殊情况状态转移覆盖「删除、插入、替换」三种操作相比纯递归动态规划通过迭代填充 DP 表时间复杂度O(m∗n)无重复计算相比记忆化递归无需递归调用栈效率更高。