东新 发表于 2025-6-4 19:33:27

线性dp：编辑距离

编辑距离


[*]本题与力扣72.编辑距离题意一样，阅读完本文可以尝试leetcode72.
力扣题目链接
题目叙述

输入两个字符串a，b。输出从字符串a修改到字符串b时的编辑距离
输入

NOTV
LOVER输出

4题目解释：


动态规划思路


[*]这个问题显然是一个最优解问题，我们可以考虑动态规划的思路，那么我们使用动态规划的思路，要想得到最优解问题，那么我们必须要先考虑子问题。
[*]子问题：我们先考虑a到b的编辑距离
状态变量的含义


[*]设立一个dp数组，作为我们的状态变量

[*]dp表示以从a到b的编辑距离

递推公式


[*]设立完状态变量，那么我们就进入了递推公式的推导

[*]1.若a=b，那么dp==dp
[*]2.a!=b



[*]那么我们就很容易的推出我们的递推公式：

[*]dp=dp（a==b）
[*]dp=min(dp,dp,dp)+1）（a!=b）

遍历顺序


[*]显然是从上到下，从左到右。
初始化dp数组


[*]边界条件：

[*]f=i
[*]f=j

[*]对应的初始化代码如下：
m=strlen(a);n=strlen(b);for(int i=1;i

硫辨姥 发表于 2025-12-14 10:58:54

谢谢楼主提供！

琦谓 发表于 2025-12-31 11:55:22

前排留名，哈哈哈

支智敏 发表于 2026-1-13 14:08:43

鼓励转贴优秀软件安全工具和文档！

虹姥 发表于 2026-1-14 21:36:12

谢谢楼主提供！

嫁吱裨 发表于 2026-1-14 22:38:17

前排留名，哈哈哈

缍米 发表于 2026-1-18 17:56:26

懂技术并乐意极积无私分享的人越来越少。珍惜

肇默步 发表于 2026-1-19 01:24:18

新版吗？好像是停更了吧。

晚能 发表于 2026-1-23 07:49:36

感谢分享，学习下。

官厌 发表于 2026-1-24 01:32:44

前排留名，哈哈哈

讣丢 发表于 2026-1-26 09:39:07

感谢分享，下载保存了，貌似很强大

骆贵 发表于 2026-1-27 02:32:18

感谢分享

倘伟 发表于 2026-1-27 03:51:27

这个好，看起来很实用

舒菀菀 发表于 2026-1-27 07:21:49

感谢分享

替攀浮 发表于 2026-1-30 05:12:08

分享、互助 让互联网精神温暖你我

第璋胁 发表于 2026-1-30 06:12:27

感谢分享

赵淳美 发表于 2026-2-3 10:15:01

感谢分享，学习下。

郏琼芳 发表于 2026-2-9 23:57:47

收藏一下   不知道什么时候能用到

褐洌 发表于 2026-2-10 06:39:41

感谢发布原创作品，程序园因你更精彩

些耨努 发表于 2026-2-10 12:33:16

鼓励转贴优秀软件安全工具和文档！
页: [1] 2
查看完整版本: 线性dp：编辑距离