902. 最短编辑距离

题意

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。
思路

三种操作：
- 删：先让1~(i-1) 和1~j相等，这样删除i才有意义
- 添：当添加的字母和b[j]相等，这样添加才有意义，那么添之前的情况就是1~i和1~(j-1)相等
  - 其实就等价于删除j
- 改：先让1~(i-1)和1~(j-1)相等，这样改才有意义
  - 如果a[i] != b[j]，才加1
dp数组初始化
- 当求最小值时，推荐将dp数组全存成INF，这样dp时直接更新即可
- 当求最大值时，推荐将dp数组全存成0
dp数组边界初始化
- 一定要结合集合定义考虑边界的含义
- 当dp数组时一维时，dp[0]需要初始化
- 当dp数组时二维时，dp[0~n][0], dp[0][0~m]需要初始化
- 以后同理
关于dp数组的max或min，是否带上自己
比如 $dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)$ 就是带上了自己
这不仅跟递推式有关，也跟是否遍历多次有关
- 如果会遍历多次，那肯定要带上自己
- dp[i][j]第一次遍历且只遍历一次，那么就不用带

代码

'''
Author: NEFU AB-IN
Date: 2022-03-07 17:01:46
FilePath: \ACM\Acwing\902.py
LastEditTime: 2022-03-07 17:16:51
'''
N = 1100
INF = int(2e9)
dp = [[INF] * N for _ in range(N)]

n = int(input())
a = " " + input()
m = int(input())
b = " " + input()

for i in range(m + 1):
    dp[0][i] = i  #初始化：当a的前0个字母想匹配b的前i个字母时，只能用添加操作，所以bi有多少字母，a就有几步
for i in range(n + 1):
    dp[i][0] = i  #初始化：当b的前0个字母想匹配a的前i个字母时，只能用删除操作，所以ai有多少字母，b就有几步

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1) #这里就不用和dp[i][j]取最小值
        # 因为dp[i][j]第一次遍历且只遍历一次
        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (1 if a[i] != b[j] else 0))

print(dp[n][m])

902. 最短编辑距离

题意

思路

代码