线性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]