路径（JAVA）

题目：

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

运行限制
最大运行时间：1s
最大运行内存: 128M

代码：

public class Main {
    public static void main(String[] args) {
        int n=2022;
        int[] dp=new int[n];              //n设为2022数组从1开始dp方便计算
        for (int i=0;i<n;i++){
            dp[i]=Integer.MAX_VALUE;       //给数组每个值都赋最大值，避免对接下来比较造成影响。
        }
        dp[1]=0;                           //初始dp[1]赋值为1（dp数组的含义思路里会提到）
        for (int i=1;i<=2020;i++){
            for (int j=i+1;j<n&&(j-i<=21);j++){
                dp[j]=Math.min(dp[j],dp[i]+f(i,j));  //从1开始将到达每个点的最短路径进行存储
            }
        }
        System.out.println(dp[2021]);     //输出dp[2021]
    }
    public static int f(int a,int b){  //求两个数的最小公倍数
        int c=0,d=a,e=b;
        while(a%b!=0){
            c=a%b;
            a=b;
            b=c;
        }
 
        return d*e/b;
    }
}