[编程题]跳石板

我就是我 2022-09-30 12:59 128阅读 0赞

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......

这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。如果不能到达，输出-1。

例如：  
N = 4，M = 24：  
4->6->8->12->18->24

于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

思路：

一开始看到题目，我想到可以建立一棵树，根结点的值是N。对于一个结点p，从小到大计算结点p的除了1和它本身的约数，每个约数生成一棵子树，子树的根结点的值是p的值加上对应的约数。以此类推……

当有某个结点的值是M，则返回该结点的层数（根结点为第0层）；当发现某一层所有的结点的值都大于M时，则返回-1，不能到达。

但是这个实现起来有些复杂，在网上看到有更好的方法。

package com.example;
    
    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Solution {
    
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int start = sc.nextInt();//0
            int end = sc.nextInt();//end-start
            //dp[] 初始化
            int[] dp = new int[end - start + 1];
            dp[0] = 0;
            for (int i = 1; i <= end - start; i++){
                dp[i] = Integer.MAX_VALUE;
            }
            //计算dp[]
            for (int i = 0; i <= end - start; i++){
                //遍历到i时，发现i之前没有能够到达i的路径
                if(dp[i] == Integer.MAX_VALUE){
                    continue;
                }
                ArrayList<Integer> list = calDivisors(i + start);
                for (int j = 0; j < list.size(); j++){
                    int x = list.get(j);
                    //更新dp[]
                    if(i + x <= end - start){
                        dp[i + x] = Math.min(dp[i + x], dp[i] + 1);
                    }
                }
            }
            if(dp[end - start] == Integer.MAX_VALUE){
                System.out.print(-1);
            }else {
                System.out.print(dp[end - start]);
            }
        }
    
        //计算约数
        private static ArrayList<Integer> calDivisors(int current) {
            ArrayList<Integer> list = new ArrayList<>();
            //只需要试到Math.sqrt(current)，可以降低时间复杂度
            for (int i = 2; i <= Math.sqrt(current); i++){
                if(current % i == 0){
                    list.add(i);
                    //i是约数，必然有一个current/i也是约数
                    if(current / i != i){
                        list.add(current / i);
                    }
                }
            }
            return list;
        }
    }