AcWing--保险箱--＞dp

5408. 保险箱 - AcWing题库(python)

# 操作顺序不影响操作结果
# 从右往左进行操作 对于某一位操作时不会影响右边结果

# 输入
n=int(input())
a=list(map(int,input()))
b=list(map(int,input()))
# 创建dp列表
f=list([float('inf') for _ in range(3)] for _ in range(n+1))
f[n][1]=0

# dp状态 枚举每一次操作 每一次操作三种状态
# 从右往左
for i in range(n-1,-1,-1):
? ? # 每一次三种操作
? ? for j in range(3):
? ? ? ? for k in range (-9,10):
? ? ? ? ? ? for t in range(3):
? ? ? ? ? ? ? ? if a[i]+k+t-1-b[i]==(j-1)*10:
? ? ? ? ? ? ? ? ? ? f[i][j]=min(f[i][j],f[i+1][t]+abs(k))
result = min(f[0][0], f[0][1], f[0][2])
print(result)
?