云南省网站备案,虚拟主机有几种类型,宜昌网站网站建设,微商城网站建设报价题目描述
求由s串变成t串的编辑距离 在s串的开头/末尾添加一个字符#xff0c;花费p 在s串的开头/末尾添加一个s串的子串#xff0c;花费q 每次作都是基于当前的s串 s串初始为空
分析
等价于将一个字符串变为空串的过程
第一层按照长度遍历#xff08;如果按照下标i,j遍…题目描述
求由s串变成t串的编辑距离 在s串的开头/末尾添加一个字符花费p 在s串的开头/末尾添加一个s串的子串花费q 每次作都是基于当前的s串 s串初始为空
分析
等价于将一个字符串变为空串的过程
第一层按照长度遍历如果按照下标i,j遍历在考虑左子串的时候会用dp[r1,j] q更新dp[i][j]r1 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]*(n1) for i in range(n1)] # 初始化最大dp[0][0] pfor lenth in range(1, n1):for i in range(n-lenth1):j ilenth-1if i j:dp[i][j] pelse: # 右边子串for l in range(i,j1):sub_s s[l:j1]if sub_s in s[i:l]:dp[i][j] min( dp[i][j], dp[i,l-1] q ) # 左边子串for r in range(i,j1):sub_s s[i:r1]if sub_s in s[r1:j1]:dp[i][j] min( dp[i][j], dp[r1,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]
