字符串距离：一种典型动态规划

解题思路:在这个题目中，要求求两个字符串之间的最小距离，在初始化字符串的时候先分别考虑两个字符串为空的情况，当其中一个为空时，另外一个字符串对应的每一个字符的位置上都是加k（空字符与任意字符的距离），初始化完成后开始更新动规数组，其中dp[i][j]表示在A字符的前i个字符，字符B的前j个字符时，最小的字符距离，题目已经要求空字符之间的距离为0，这里就不在考虑A,B初始都是空字符的情况（因为初始化的dp数组是以0为初始项），这里需要考虑的一点就是当遇到A,B字符串中对比的字符不一样时，要考虑增添，修改，删除，三种情况，其中删除与修改两种情况需要再取一遍最小值

注意事项:min(dp[i-1][j]+k,min(dp[i][j-1]+k,dp[i-1][j-1]+abs(ord(A[i-1])-ord(B[j-1]))))中，“修改”的那一部分不要把下标写成A[i]和B[j]，因为这里dp数组不是从下标1开始存储的

参考代码:

def juli(A,B,k):
   a=len(A)
   b=len(B)
   dp=[[0]*(b+1) for _ in range(a+1)]
   #A全是空字符的情况
   for i in range(b+1):
       dp[0][i]=i*k
   #B全是空字符的情况
   for i in range(a+1):
       dp[i][0]=i*k
   for i in range(1,a+1):
       for j in range(1,b+1):
           if A[i-1]==B[j-1]:
               dp[i][j]=dp[i-1][j-1]
           else:
               dp[i][j]=min(dp[i-1][j]+k,min(dp[i][j-1]+k,dp[i-1][j-1]+abs(ord(A[i-1])-ord(B[j-1]))))
   return dp[a][b]
A=input()
B=input()
k=int(input())
print(juli(A,B,k))