字符串A->字符串B例题 :最短编辑距离、最优包含 (线性DP)

AcWing 902. 最短编辑距离

给定两个字符串A和B,现在要将A经过若干操作变为B,可进行的操作有:

  • 删除–将字符串A中的某个字符删除。
  • 插入–在字符串A的某个位置插入某个字符。
  • 替换–将字符串A中的某个字符替换为另一个字符。

现在请你求出,将A变为B至少需要进行多少次操作。

输入格式
第一行包含整数n,表示字符串A的长度。

第二行包含一个长度为n的字符串A。

第三行包含整数m,表示字符串B的长度。

第四行包含一个长度为m的字符串B。

字符串中均只包含大写字母。

输出格式
输出一个整数,表示最少操作次数。

数据范围
1≤n,m≤1000
输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例:
4

题解
状态表示 dp[i][j]

  1. 集合 : 所有把a[1~i]变成 b[1~j]的集合的操作集合
  2. 属性 : 所有操作中操作次数最少的方案的操作数

状态计算
状态划分 以对a中的第i个字母操作不同划分

  1. 在该字母之后添加
    添加一个字母之后变得相同,说明没有添加前a的前i个已经和b的前j-1个已经相同
    即 : dp[i][j] = dp[i][j-1] + 1

  2. 删除该字母
    删除该字母之后变得相同,说明没有删除前a中前i-1已经和b的前j个已经相同
    即 : dp[i][j] = dp[i-1][j] + 1

  3. 替换该字母

    • 替换说明对应结尾字母不同,则看倒数第二个
      即: dp[i][j] = dp[i-1][j-1] + 1
      啥也不做
    • 对应结尾字母相同,直接比较倒数第二个
      即: dp[i][j] = dp[i-1][j-1]
n = int(input())
s1 = input()
s1 = " " + s1
m = int(input())
s2 = input()
s2 = " " + s2

dp = [[1e18] * (m + 1) for i in range(n + 1)]

# 边界情况
# 只能删除
for i in range(1, n + 1):
    dp[i][0] = i
# 只能添加
for j in range(1, m + 1):
    dp[0][j] = j
    

dp[0][0] = 0

for i in range(1, n + 1):
    for j in range(1, m + 1):
        
        # 改
        if s1[i] == s2[j]:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
        else: dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
        
        # 删
        dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
        
        # 加
        dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
        
        
print(dp[-1][-1])
        
        

2553. 最优包含

我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列,即可以从字符串 S 中抽出若干个字符,它们按原来的顺序组合成一个新的字符串与 T 完全一样。

给定两个字符串 S 和 T,请问最少修改 S 中的多少个字符,能使 S 包含 T?

输入格式
输入两行,每行一个字符串。

第一行的字符串为 S,第二行的字符串为 T。

两个字符串均非空而且只包含大写英文字母。

输出格式
输出一个整数,表示答案。

数据范围
1≤|T|≤|S|≤1000
输入样例:
ABCDEABCD
XAABZ
输出样例:
3

题解
状态表示 dp[i][j]

  1. 集合 : 所有把a[1~i]变成 b[1~j]的集合的操作集合
  2. 属性 : 所有操作中操作次数最少的方案的操作数

状态计算
状态划分 以对a中的第i个字母操作不同划分

  1. 不变
    与上题不同,这是一个子序列。
    dp[i][j] = dp[i - 1][j]
  2. 替换该字母
    • 替换说明对应结尾字母不同,则看倒数第二个
      即: dp[i][j] = dp[i-1][j-1] + 1
      啥也不做
    • 对应结尾字母相同,直接比较倒数第二个
      即: dp[i][j] = dp[i-1][j-1]
s1 = input()
s2 = input()

n = len(s1)
m = len(s2)

s1 = " " + s1
s2 = " " + s2

dp = [[1e18] * (m + 1) for i in range(n + 1)]
for i in range(0, n + 1):
    dp[i][0] = 0 

for i in range(1, n + 1):
    for j in range(1, m + 1):
        
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if s1[i] == s2[j]:
            dp[i][j] = min(dp[i][j], dp[i-1][j-1])
        else:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
print(dp[-1][-1])
上一篇:恋上数据结构与算法第三季课堂笔记05


下一篇:C++STL标准库学习笔记(八)string