20220820美团笔试问题
第四题变化版的编辑距离，明明很简单，自己试了几个用例也是对的。但是我代码一直ac不了，大佬们帮我看看哪里有问题
n,m = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))
dp = [[0]*(m+1) for _ in range(n+1)]
# dp[i][j]表示A[i-1],B[j-1]的修改距离
# 初始化
for i in range(1,n+1):
dp[i][0] = dp[i-1][0]+abs(A[i-1])
for j in range(1,m+1):
dp[0][j] = dp[0][j-1]+abs(B[j-1])
# 状态转移
for i in range(1,n+1):
for j in range(1,m+1):
if A[i-1]==B[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1]+abs(B[j-1]), dp[i-1][j]+abs(A[i-1]),dp[i-1][j-1]+abs(A[i-1]-B[j-1]))
print(dp[-1][-1]) 
投递虾皮信息等公司10个岗位 >
携程公司氛围 85人发布
