欢迎大家阅读本文章
如果大家对LCM和GCD不是很熟悉，这篇文章将对你有帮助！
本文章也会把动态规划做一定的介绍
题目：
GCD和LCM的讲解：
GCD的实现-辗转相除法：
在数学中，辗转相除法，又称欧几里得算法（Euclidean algorithm），是求取最大公约数的一种算法。辗转相除法首次出现于欧几里得的《几何原本》中的第Ⅶ卷，书中的命题ⅰ和命题ⅱ所描述的就是辗转相除法，而在中国，辗转相除法最早出现在《九章算法》中。
希腊数学家是这样处理的，在我们预先构造的矩形中，我们先以矩形的短边构造正方形，然后再去计算这样的正方形可以在大矩形中「最多」放置多少个，这个计算过程可以用取余的方式进行计算。接下来，我们再用长边余下的长度构建正方形，在去试图铺满剩下未被覆盖的部分，然后计算这个正方形最多可以放置几个，直到我们找到这样一个正方形，这个正方形可以完全铺满整个大矩形。那么这个正方形就是我们最终要找的答案，自然而然的，这个正方形的边长也就是我们要找的两数的最大公约数。
具体了解可以看这篇文章
LCM的实现：
算法分解定理： 任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 N=P1a1 P2a2P3a3…Pnan，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。
所以可以推导出：gcd(a, b) * lcm(a, b) = a * b
代码实现：
def gcd(a, b):
if b == 0: return a
return gcd(b, a % b)
def lcm(a, b):
return a * b // gcd(a, b)️注意：python里的math库有gcd()，可以直接调用，但是蓝桥杯的系统没有lcm()方法！新版的python有lcm()方法，为了保险起见，在做题的时候，lcm()需要手写一遍。
动态规划讲解：
DP是一种容易理解的计算思想。有一些问题有两个特征：重叠子问题、最优子结构。用DP可以高效率的处理具有这两特征的问题。
重叠子问题：
子问题是大问题的小版本，它们的计算步骤完全一样。计算大问题的时候，需要重复计算小问题。这就是重叠子问题。
最优子结构：
最优子结构的意思是，大问题的最优解；可以通过小问题的最优解推导出大问题的最优解。
DP的过程一般需要：状态设计、状态转移方程、DP代码实现、滚动数组。
题目解答：
我拿到题目的时候，有点蒙，不知道题目想要求什么。后来经过反复的读题，我恍然大悟！
题目大意是：从1结点走到2021结点的最短路径，因为结点到结点的距离是不一样，所以有很多走法，我们的目的就是找到路径最短的一条。题目中还有限制条件，就是结点差不能大于21，也就是每次从n个结点最远走到n+21结点。然后题目规定了，结点到结点之间到距离是两个结点的最小公倍数。
看来出题人很有心思啊！如果不会求最大公约数（GCD）和最小公倍数（LCM），又不会用动态规划（DP），三者少一者，这题都做不出来！
from math import * # gcd()是math库里的方法
def lcm(i, j): # 手写lcm()
return (i * j) // gcd(i, j)首先写个lcm()，方便后续求两个结点的路径。
INF = 1<<100 # 模拟无穷大
dp = [INF] * 2022构建线性dp，用来存放走到 i 结点时最短的路径dp[i]
# 特殊值处理
for i in range(1, 23):
dp[i] = i对于特殊的结点 i，我们直接赋值给它。为什么特殊呢？因为结点1到结点22，它们的最短路径都是它们本身。也是为了写后面的代码少个判断，能偷个懒。
# dp找最短路径
for i in range(23, 2022):
for j in range(i-21, i):
tmp = dp[j] + lcm(i, j)
if tmp < dp[i]: dp[i] = tmp这里我们可以看到第二层for循环 j 是从i - 21开始的，所以第一层for循环 i 是从23开始，前面的1到22我单独写了层循环赋值。 假设 i == 25 的时候，我们的目的就是要求出1到25结点之间到最短距离，倒数第二个结点到最后一个结点最多差21，举个例子：结点3不能直接到结点25，因为它们的结点差大于21，所以可以是从4结点到25结点，从5结点到25结点……24结点到25结点。
第二个for循 j 的目的就是找倒数第二个结点到最后一个结点 i 的最短路径，每次求出的路径用tmp变量记录，如果tmp比dp[i]小的话，dp[i] = tmp。
如果还不能理解的话看下面的模拟：
题目：找出结点1到结点25之间到最短路径（限制条件和上面说的一样）
分析：dp[1]~dp[22]的值都是它们的索引（1和任意数 a 的最小公倍数都是a）
dp[23] = dp[2] + lcm(2, 23) = 48 这是dp[23]最小的情况
dp[24] = dp[4] + lcm(4, 24) = 28 这是dp[24]最小的情况
dp[25] = dp[5] + lcm(5, 25) = 30 这是dp[25]最小的情况
如果之后数据量大的时候，后面的dp[x]可以直接调用前面的dp[y]。
这也是一种最优子结构。
完整代码：
from math import *
def lcm(i, j):
return (i * j) // gcd(i, j)
INF = 1<<100
dp = [INF] * 2022
# 特殊值处理
for i in range(1, 23):
dp[i] = i
# dp找最短路径
for i in range(23, 2022):
for j in range(i-21, i):
tmp = dp[j] + lcm(i, j)
if tmp < dp[i]: dp[i] = tmp
print(dp[2021])
完结撒花祝每个奋斗的人都能成功！
