第十二届蓝桥杯JavaB组省赛真题 - 路径
解题思路:
动态规划
需要熟练掌握最小公倍数和最大公约数的计算
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);}
}