题解 | #跳石板#

import java.util.*;

import java.util.List;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m = in.nextInt();
        int[] step = new int[m +1]; //抛弃0下标,我们从1下标开始,这样可以和n,m对应
        for (int i = 0; i < m + 1; i++) {
            step[i] = Integer.MAX_VALUE; //先赋值,为了等下区分
        }
        step[n] = 0; //先把n下标定位为,因为是从n开始的,是第0步
        for (int i = n; i < m; i++) { //从n下标开始,到m下标结束
            if (step[i] == Integer.MAX_VALUE) { //代表走不到这里
                continue;//跳过当前i
            }
            //代表可以走到这里
            //获取约数
            List<Integer> list = div(i);
            for (int j :list) { //遍历得到的约数集合,j代表了往后面走的步数
                if (i + j <= m && step[i + j] == Integer.MAX_VALUE) { //代表还没有到达
                    step[i + j] = step[i] + 1; //为前一步的加一
                } else if (i + j<= m &&step[i + j] != Integer.MAX_VALUE){//代表下面一步已经有人走了
                step[i+j] = Math.min(step[i + j],step[i] +1); //原有的路径步数和当前的再往后面走一步比较
                }
            }
        }
        if (step[m] == Integer.MAX_VALUE) {
            System.out.print(-1);//代表走不到
        } else {
            System.out.print(step[m]);
        }
    }
    //求约数的方法
    public static List<Integer> div(int num) {
        List<Integer> list = new ArrayList<>(); //存储约数
        for (int i = 2; i * i <= num;i++) { //约数不包括1和自己,而且只这里只求前面一块的
            if (num % i == 0) { //能被整除,代表是约数
                list.add(i);//约数放入集合
                if (num / i != i) {
                    list.add(num /i); //把另外一半放入集合,前提是两个约不相等(2×3放两次  4×4放一次)
                }
            }
        }
        return list;
    }
}

以例子举例:()里面代表从哪里走到当前下标的

--->1,从4下标开始,求得4的约数2,然后4往下走两步到6,

--->2,然后从6开始找约数:2,3,这时候分开两头走,可以走两步到8也可以走3步到9,

--->3,从8开始约数为2或4,到10和12 或者从9开始约数为3,到12

--->4,从10开始约数为2,5到12或15 或者从12开始约数为2,3,4,6到14,15,16,18

............

--->此时我们可以看到到达12的话可以是3步也可以是4步,那么我们需要最优的解,那当然就是3步了

--->总结出:我们可以走每一步(每一个约数都走一遍),但是在每一位下标下面存储的次数是只存储最小的次数,3步4步都可以到,那就是3步到的路径

--->不管哪条路径,只要你们到达同一个下标的位置,就代表在这里重合了,既然你们都可以到,那么我只要最短的

--->余下步骤以此类推

实现:

--->我们先定义m+1长度的数组:这是为了抛弃0下标,让我们可以让n下标就是n位置,m同样(我们下标

0到m--->1到m+1),m+1下标代表我们从1开始的m位置的元素

然后把数组每一个元素都赋相同的值,

--->定义n下标元素为0(因为是从n开始的,所以步数为0)

//走一遍理解

--->遍历数组元素(从n开始到m结束),首先因为是从n开始的,所以n下标的元素一定是0,我们找到n的约数,然后让n+约数下标的元素的值变为(0+1)(步),代表走一步到达这里,然后后面的以此类推,

---->但是切记,当多条路径重合的时候,我们的下标的元素值只取最小的那一步

核心实现:遍历数组元素,若当前下标元素是我们一开始设定的初始值,则代表不论哪条路径都达不到这里(从n开始,n下标加上的约数,那么n+1的下标元素可能就还是初始值),跳过,继续到下一位下标,比较是否是初始值

--->若不是的话,则代表当前下标可以有路径到达(且一定是最短的),

--->所以我们要比较(i+j)下标元素的大小(从当前下标走到下一步的位置), //j代表当前下标的约数

--->若i+j下标元素为初始值,则代表这是一条路径(从i下标走到i+j下标),若不是初始值,则代表i+j下标已经有路径到达了,所以我们要比较i+j下标原有的步数和我们现在走到i+j下标的步数,取最小值

--->就这样一直走下去,最后若m下标元素为初始值,则代表走不到m反之,m下标元素就是最小步数

--->怎么比较i+j下标元素的值

i+j原有的元素值和当前i下标的元素值+1(代表从i下标走到i+j下标走了一步)进行比较