第十四届蓝桥杯大赛省赛Python——保险箱_蓝桥杯保险箱

一、问题描述

二、算法思想

本题涉及到最少次数问题，因可以考虑用贪心法或者是动态规划问题，但仔细分析题目，这个题目要求我们操作密码次数最小，我们可以将问题划分成一个个子问题，即求解每一位密码打到目标数字所需的最少操作步数，下一位密码在上一位密码最少操作步数的基础上再进行求解，很明显我们可以采取动态规划的算法，每一位密码达到目标状态可以有三种操作：即不进位、不退位；通过进位；通过退位，具体可看下图例子：

根据例子可以写出动态规划转移方程dp[ i ] [ j ]，i表示第i位密码，j表示第j种状态，每一种状态在上一种状态上进行运算、比较

不进位、不退位：dp[i][0]=min(dp[i-1][0] + abs(x[i]-y[i]), dp[i-1][1] + abs(x[i]+1-y[i]), dp[i-1][2]+abs(x[i]-1-y[i]))

进位：dp[i][1]=min(dp[i-1][0] + 10-x[i]+y[i], dp[i-1][1] + 10-(x[i]+1)+y[i], dp[i-1][2] + 10-(x[i]-1)+y[i])

退位：dp[i][2]=min(dp[i-1][0] + 10-y[i]+x[i], dp[i-1][1] + 10-(y[i]-1)+x[i], dp[i-1][2] +10-(y[i]+1)+x[i])

二、代码实现（附注释）

#保险箱(动态规划算法)
n=int(input())
x=[0]+list(map(int,list(input())))[::-1]#逆序，方便高位进位运算
y=[0]+list(map(int,list(input())))[::-1]
dp=[[0]*3 for i in range(n+1)]#生成dp数组
#定义dp数组初始值
dp[1][0]=abs(x[1]-y[1])  #不进位，不退位
dp[1][1]=10-x[1]+y[1]   #进位
dp[1][2]=10-y[1]+x[1]   #退位
for i in range(2,n+1):
    dp[i][0]=min(dp[i-1][0] + abs(x[i]-y[i]), dp[i-1][1] + abs(x[i]+1-y[i]), dp[i-1][2]+abs(x[i]-1-y[i])) #不进位，不退位
    dp[i][1]=min(dp[i-1][0] + 10-x[i]+y[i], dp[i-1][1] + 10-(x[i]+1)+y[i], dp[i-1][2] + 10-(x[i]-1)+y[i]) #进位
    dp[i][2]=min(dp[i-1][0] + 10-y[i]+x[i], dp[i-1][1] + 10-(y[i]-1)+x[i], dp[i-1][2] +10-(y[i]+1)+x[i]) #退位
# print(dp)
print(min(dp[n][0],dp[n][1],dp[n][2]))