2021年第十二届蓝桥杯省赛Python组（真题+解析+代码）：路径_第12届蓝桥杯stema真题 python

1 真题

2 解析

难度系数：⭐⭐

考察题型：数论  动态规划　

涉及知识点：最小公倍数 最短路径 

思路分析：

这道题可谓是究极嵌套！融合了最短路径，最小公倍数和动态规划。一个不会就全凉了~

最小公倍数我已经整理成精简模板放代码里了，考试时直接套模板就行。

动态规划经典的做题步骤有5步。

 第一步：明白dp[i]的含义

 dp[i]　#i:结点编号1~2021 #dp[i]:当前结点到结点1的最短路径长度

第二步：给dp数组初始化赋值

dp=[float('inf')]*(n+1)         #创建列表赋值为无穷大
dp[1]=0                         #结点1的长度初始化为0

第三步：弄清dp[i]遍历的顺序

for i in range(1,n+1):          #先遍历结点a：遍历结点1~n
    for j in range(i+1,i+22):   #再遍历结点b：遍历结点i+1~i+21

第四步：搞懂递推公式

dp[j]=min(dp[j],dp[i]+lcm(i,j))  #递推公式

第五步：打印数组

print(dp[n])                    #输出结果：10266837

参考资料：

python的动态规划我是看这个视频学的，学会里面的经典案例，动态规划一通百通~

清华计算机博士带你学习Python算法+数据结构_哔哩哔哩_bilibili

3 代码

#最小公倍数模板(least common multiple)
def lcm(a,b):
    if a<b:   
        a,b=b,a
    c,d=a,b 
    while d!=0:
        c,d=d,c%d
    return (a*b)//c
 
#最短路径(dp)
n=2021                          #结点数量
dp=[float('inf')]*(n+1)         #创建列表赋值为无穷大
dp[1]=0                         #结点1的长度初始化为0
for i in range(1,n+1):          #结点a：遍历结点1~n
    for j in range(i+1,i+22):   #结点b：遍历结点i+1~i+21
        if j>n:                 #j超出结点范围时
            break               #结束循环
        dp[j]=min(dp[j],dp[i]+lcm(i,j))#递推公式
print(dp[n])                    #输出结果：10266837