线性dp：编辑距离

编辑距离

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

题目叙述

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

1. NOTV
2. LOVER

复制代码

输出

1. 4

复制代码

题目解释：

动态规划思路

• 这个问题显然是一个最优解问题，我们可以考虑动态规划的思路，那么我们使用动态规划的思路，要想得到最优解问题，那么我们必须要先考虑子问题。
  
• 子问题：我们先考虑a[1,2...i]到b[1,2....j]的编辑距离
  

状态变量的含义

• 设立一个dp数组，作为我们的状态变量
  
  
  
  • dp[j]表示以从a[1...i]到b[1....j]的编辑距离
    
  
  

递推公式

• 设立完状态变量，那么我们就进入了递推公式的推导
  
  
  
  • 1.若a=b[j]，那么dp[j]==dp[i-1][j-1]
    
  • 2.a!=b[j]
    
  
  

• 那么我们就很容易的推出我们的递推公式：
  
  
  
  • dp[j]=dp[i-1][j-1]（a==b[j]）
    
  • dp[j]=min(dp[i-1][j-1],dp[j-1],dp[i-1][j])+1）（a!=b[j]）
    
  
  

遍历顺序

• 显然是从上到下，从左到右。
  

初始化dp数组

• 边界条件：
  
  
  
  • f[0]=i
    
  • f[0][j]=j
    
  
  
• 对应的初始化代码如下：
  

[code]m=strlen(a);n=strlen(b);for(int i=1;i