题解 | #计算字符串的距离#

解题思路：
动态规划
1.dp[i][j]定义
字符串A[0~i]和字符串B[0~j]的编辑距离
2.状态转移方程
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+t)
其中t当A[i] == B[j]时为1，其它为0
3.边界
dp[0][0] = 0
dp[0][j] = j
dp[i][0] = i
#=============================================================================================
'''

#a = input()
#b = input()

a = 'abcdefg'
b = 'abcdef'

n = len(a)
m = len(b)
DP = [[0]*(m+1) for _ in range(n+1)]

for i in range(n+1):
    DP[i][0] = i
for j in range(m+1):
    DP[0][j] = j
DP[0][0] = 0
    # print(DP)

for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i-1] == b[j-1]:
            t = 0
        else:
            t = 1
        DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+t)
print(DP[-1][-1])