# 《算法技术手册》一3.6.3 动态规划

#### 3.6.3 动态规划

def minEditDistance(s1, s2):
"""计算将s1转换到s2的最小编辑距离"""
len1 = len(s1)
len2 = len(s2)

m = [None] * (len1 + 1)
for i in range(len1 + 1):

m[i] = [0] * (len2 + 1)


for i in range(1, len1 + 1):

m[i][0] = i

for j in range(1, len2 + 1):

m[0][j] = j


for i in range(1, len1 + 1):

for j in range(1, len2 + 1):
cost = 1
if s1[i - 1] == s2[j - 1]: cost = 0
replaceCost = m[i - 1][j - 1] + cost
removeCost = m[i - 1][j] + 1
insertCost = m[i][j - 1] + 1
m[i][j] = min(replaceCost, removeCost, insertCost)

return mlen1

REPLACE = 0
REMOVE = 1
INSERT = 2
def minEditDistance(s1, s2):
"""计算将s1转换到s2的最小编辑距离，并且记录操作顺序 """
len1 = len(s1)
len2 = len(s2)

m = [None] * (len1 + 1)
op = [None] * (len1 + 1)
for i in range(len1 + 1):

  m[i] = [0] * (len2 + 1)
op[i] = [-1] * (len2 + 1)


for j in range(1, len2 + 1):

  m[0][j] = j

for i in range(1, len1 + 1):

  m[i][0] = i


for i in range(1, len1 + 1):

for j in range(1, len2 + 1):
cost = 1
if s1[i - 1] == s2[j - 1]: cost = 0
replaceCost   = m[i - 1][j - 1] + cost
removeCost    = m[i - 1][j] + 1
insertCost    = m[i][j - 1] + 1
costs         = [replaceCost, removeCost, insertCost]
m[i][j]       = min(costs)
op[i][j]      = costs.index(m[i][j])

ops = []
i = len1
j = len2
while i != 0 or j != 0:

if op[i][j] == REMOVE or j == 0:
ops.append('remove {}-th char {} of {}'.format(i,s1[i-1],s1))
i = i - 1
elif op[i][j] == INSERT or i == 0:
ops.append('insert {}-th char {} of {}'.format(j,s2[j-1],s2))
j = j - 1
else:
if m[i - 1][j - 1] < m[i][j]:
fmt='replace {}-th char of {} ({}) with {}'
ops.append(fmt.format(s1, i, s1[i - 1], s2[j - 1]))
i, j = i - 1, j - 1

return mlen1, ops

|
5天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
21 1
|
5天前
|

【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
12 1
|
7天前
|

14 1
|
7天前
|

Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法，它产生更平滑的颜色过渡。数学公式表示为：mu = n + 1 - log(log(|Z(n)|)) / log(p)，其中 Z(n) 是迭代次数，|Z(n)| 是复数模长，p 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
11 3
|
9天前
|

LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
8 0
|
9天前
|

15 3
|
9天前
|

LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
17 4
|
9天前
|
SQL 算法 数据可视化
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
6 0
|
9天前
|

5 0
|
11天前
|

13 0