字符串的扩展距离问题--------动态规划算法

文章目录

前言
一、字符串的扩展距离问题 (给出问题)
二、分析
- 1.状态转移方程的由来
三、代码
总结

前言

学无止境，笔勤不辍。最近笔者又闲了下来，于是抽空在课上写一篇关于动态规划思想的典型问题(最近遇到的奇奇怪怪的问题，困扰了笔者一段时间)。希望能给大家一些帮助和启示…

一、字符串的扩展距离问题 (给出问题)

对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0，空格与其他字符的距离为一定值k。
在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。
算法要求如下
1、数据输入：第1行是字符串A，第2行是字符串B，第3行是空格与其他字符的距离定值k。
2、输出：字符串A和B的扩展距离。
例如
输入：
cmc
snmn
2
输出：10

注：设字符串A和B的子串A[1…i]和B[1…j]的扩展距离为val(i,j)，则val(i,j)具有最优子结构性质，递归定义为：val(i,j)=min{val(i-1,j)+k, val(i,j-1)+k, val(i-1,j-1)+dist(ai,bj)}

二、分析

1.状态转移方程的由来

val(i,j)=min{val(i-1,j)+k, val(i,j-1)+k, val(i-1,j-1)+dist(ai,bj)}
分析：
为了比较字符串A,B之间的扩展距离，有三种情况：
假设A字符串下标是1,2…,i B字符串下标是1,2…,j
1.若i是空格，j是字符，则扩展距离是val(i-1,j)+k
2.若j是空格，i是字符，则扩展距离是val(i,j-1)+k
这两种情况，为什么是val(i-1,j)/val(i,j-1)，它们中的j和i是为什么出现，这里给出笔者自己的思考
无论是i是空格或者j是空格，对另一个字符串的排序并没有产生差别，因此，val(i,j)只是在前面拓展距离的基础上增加一个k的代价，因此在问题中应该出现i/j
3.若j是字符，i是字符，则扩展距离是val(i-1,j-1)+dist(ai,bj) dist是指两字符的ASCII编码之差。
比较它们三者，取最小值，使得动态规划不遗漏各种情况且取到当前的全局最优…

三、代码

def calculate_distance(A, B, k):m, n = len(A), len(B)dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]dp[0][0] = 0for i in range(1, m + 1):dp[i][0] = dp[i - 1][0] + kfor j in range(1, n + 1):dp[0][j] = dp[0][j - 1] + kfor i in range(1, m + 1):for j in range(1, n + 1):if A[i - 1] == ' ' and B[j - 1] == ' ':cost = 0elif A[i - 1] == ' ' or B[j - 1] == ' ':cost = kelse:cost = abs(ord(A[i - 1]) - ord(B[j - 1]))dp[i][j] = min(dp[i - 1][j - 1] + cost, dp[i - 1][j] + k, dp[i][j - 1] + k)return dp[m][n]# 输入
A = input().strip()
B = input().strip()
k = int(input().strip())# 计算并输出扩展距离
print(calculate_distance(A, B, k))