Loading... ## 题目  ## 思路 dist[i]代表从1到i的最短路径。gcd是求最大公约数,lcm是求最小公倍数。 先把从1到2-21之间的距离算出来存到dist里,然后算之后的路径。 之后的22-2021,用动态规划的思想,dist[i]就取从i的前21个点到i的最短路径,依次可以算到2021,得到最终答案。 这种方法应该是比较简单的了,速度也不慢。 ## 题解 ```Python def gcd(a,b): while(a % b != 0): a,b = b,a % b return b def lcm(a,b): return a*b//gcd(a,b) dist = [0 for i in range(2022)] for i in range(2,22): dist[i] = lcm(1,i) for i in range(22,2022): dist[i] = min([dist[j] + lcm(j,i) for j in range(i-21,i)]) print(dist[2021]) ``` 输出结果 ``` 10266837 ``` Last modification:March 14, 2022 © Allow specification reprint Support Appreciate the author WeChat Like 0 如果觉得我的文章对你有用,请随意赞赏