解题思路:
动态规划
需要熟练掌握最小公倍数和最大公约数的计算
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] dp = new int[2022];
dp[1] = 0;
for (int i = 2; i <= 2021; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 1; i <= 2020; i++) {
for (int j = i + 1; j <= 2021 && (j - i <= 21); j++) {
dp[j] = Math.min(dp[i] + le(i, j), dp[j]);
}
}
System.out.print(dp[2021]);
}
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static int le(int a, int b) {
return a * b / gcd(a, b);
}
}