蓝桥杯|2021年第十二届蓝桥杯省赛Python组（真题+解析+代码）（路径）算法|职场和发展|动态规划|p

1 真题
文章图片
2 解析难度系数：??
【蓝桥杯|2021年第十二届蓝桥杯省赛Python组（真题+解析+代码）（路径）】考察题型：数论动态规划
涉及知识点：最小公倍数最短路径

思路分析：
这道题可谓是究极嵌套！融合了最短路径，最小公倍数和动态规划。一个不会就全凉了~
最小公倍数我已经整理成精简模板放代码里了，考试时直接套模板就行。
动态规划经典的做题步骤有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 an:#j超出结点范围时 break#结束循环 dp[j]=min(dp[j],dp[i]+lcm(i,j))#递推公式 print(dp[n])#输出结果：10266837

我写的是关于蓝桥杯的系列题解，感谢关注我的朋友们，我会持续输出高质量文章
蓝桥杯python组十二届省赛真题+解析+代码（通俗易懂版）_编程有了思路-CSDN博客_蓝桥杯大赛python小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少？https://blog.csdn.net/m0_55148406/article/details/122774029