算法-线性DP模板题-902. 最短编辑距离

本文主要是介绍算法-线性DP模板题-902. 最短编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

思路

1. 本题采用闫式DP分析法
   状态表示：
   1.集合：所有将a[1-i]变成b[1-j]的操作方式
   2.属性:min
   状态计算：
   

代码
 

n=int(input())
a=list(map(str,input()))
m=int(input())
b=list(map(str,input()))
a.insert(0,'0')
b.insert(0,'0')
f=[[0 for _ in range(1010)] for _ in range(1010)]
for j in range(0,m+1):f[0][j]=j # 添加操作
for i in range(0,n+1):f[i][0]=i # 删除操作
for i in range(1,n+1):for j in range(1,m+1):f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1)if a[i]==b[j]:f[i][j]=min(f[i][j],f[i-1][j-1])else :f[i][j]=min(f[i][j],f[i-1][j-1]+1)print(f[n][m])

这篇关于算法-线性DP模板题-902. 最短编辑距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---