目录
一、题目描述
小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3…….
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板输入描述：
输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)
输出描述：
输出小易最少需要跳跃的步数,如果不能到达输出-1
测试用例：
输入：4 24
输出：5
二、思路解析
1、从编号为n的石板跳到编号为m的石板，其中跳的石板数为n的约数（不包括1和n本身）
2、将编号为0到m的石板数用组arr来记录从编号n跳到编号m的石板所需的步数，使其编号与数组下标一一对应，即数组长度为m+1，同时对数组每一个元素赋值为默认值Integer.MAX_VALUE(方便判断编号n的石板跳的每一个约数步数到达的石板是否被其他约数步数跳过）
3、初始化编号为n的石板所需步数为0（arr[n]=0），即从编号为n的石板开始跳
4、从编号为n的石板跳到编号为m的石板的过程中，每一步跳的石板数为n的约数，因此定义一个求编号n的约数（不包含1和n本身）的方法
5、当从编号为n的石板每一步跳的石板数所对应的数组元素为默认值时，即没有被其他约数步数跳过，即修改此时对应的数组元素为步数+1=arr[i]+1；反之对应的数组元素不为默认值时，即已经被其他约数步数跳过了，比较这两个约数步数的最小值(arr[i+j] = Math.min(arr[i+j],arr[i]+1)
6、当遍历完从编号为n的石板到编号为m的石板，如果arr[m]==元素默认值，即石板m无法从石板n跳到，返回-1；反之输出arr[m]对应的步数
思路图解：
三、题解代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[] arr = new int[m+1];//创建出一个数组arr，在arr数组，里面存放的是跳石板的次数，在这里我们初始化为整数的最大值
for(int i=0;i<arr.length;i++){
arr[i] = Integer.MAX_VALUE;//初始化每个数组元素为默认最大值
}
arr[n]=0; //定义此时从编号为n的石板开始跳
for(int i=n;i<arr.length;i++){
if(arr[i] ==Integer.MAX_VALUE ){ //此处为跳到那些默认的石板，则继续遍历
continue;
}
//调用求编号为i的石板的约数的方法func
List<Integer> list = func(i);
for(int j : list){//遍历约数j，求每跳一个约数石板，步数+1
if(i+j <= m && arr[i+j] != Integer.MAX_VALUE){
//当跳石板的位置不是默认数值，说明这块石板有其他约数已经跳过了，
// 即比较其他约数的步数与此时的步数最小值
arr[i+j] = Math.min(arr[i+j],arr[i]+1);
}else if(i+j <= m){
//当跳石板的位置是默认数值，即这块石板没有被其他约数跳过，即步数=此时步数+1
arr[i+j]=arr[i]+1;
}
}
}
if(arr[m] == Integer.MAX_VALUE){//说明此时编号为m的石板无法跳到
System.out.println(-1);
}else{
System.out.println(arr[m]);//输出此时编号为m的石板的步数
}
}
public static List<Integer> func(int sum){ //求编号为m石板的约数
List<Integer> list = new ArrayList<>();
for(int i=2;i<sum;i++){//题目要求为不包含1和本身的约数，所以从2开始
if(sum % i == 0){ //若能整除i，则i为约数
list.add(i);
if(sum/i != i ){//当能整除i且商不等于i，则商也是约数
list.add(sum/i);
}
}
}
return list;
}
}
四、牛客链接