东新 发表于 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
页: [1]
查看完整版本: 线性dp:编辑距离