【将字符串变为空的编辑距离】

题目描述

求由s串变成t串的编辑距离
在s串的开头/末尾添加一个字符，花费p
在s串的开头/末尾添加一个s串的子串，花费q
每次作都是基于当前的s串
s串初始为空

分析

等价于将一个字符串变为空串的过程

第一层按照长度遍历（如果按照下标i,j遍历，在考虑左子串的时候，会用dp[r+1,j] + q更新dp[i][j]，r+1 >=i, 会出现用未知值算未知值的情况）

考虑每一种状态转移：左子串，右子串，左开头，右开头

代码

# 求由s串变成t串的编辑距离
# 在s串的开头/末尾添加一个字符，花费p
# 在s串的开头/末尾添加一个s串的子串，花费q
# 每次作都是基于当前的s串
# s串初始为空# dp[i][j] 代表 从下标i的字符开始，到下标j的字符结束的子串 变为空需要的最小花费# 按照长度，考虑下标的边界情况，
# 转移时不能直接复制，取min
# 相同的数据类型进行比较def ans(s:str, p:int, q:int):n = len(s)dp = [[1e9]*(n+1) for i in range(n+1)] # 初始化最大dp[0][0] = pfor lenth in range(1, n+1):for i in range(n-lenth+1):j = i+lenth-1if i == j:dp[i][j] = pelse:              # 右边子串for l in range(i,j+1):sub_s = s[l:j+1]if sub_s in s[i:l]:dp[i][j] = min( dp[i][j], dp[i,l-1] + q )  # 左边子串for r in range(i,j+1):sub_s = s[i:r+1]if sub_s in s[r+1:j+1]:dp[i][j] = min( dp[i][j], dp[r+1,j] + q)  # 取min# 删一个字符dp[i][j] = min(dp[i][j], dp[i][j-1]+p, dp[i-1][j]+p)             return dp[0][n-1]