蓝桥杯 路径
答案
import math
def lcm(i,j):
m = math.gcd(i,j)
return i*j//m
n = 2021
dp = [float('inf')]*2022
dp[1] = 0
for i in range(1,n+1):
for j in range(i+1,i+22):
if j > n:
break
dp[j] = min(dp[j],dp[i]+lcm(i,j))
print(dp[n])对dp[j] = min(dp[j],dp[i]+lcm(i,j))的解析：
一个是已经连接好的权值的大小，一个是当前结点与上一个已经连接好的结点的权值大小的和。
因为考虑到当前结点的前一个节点的权值可能会刚刚更新，所以会想到纳入考量之中。