【算法刷题题解】跳石板动态规划（java实现）

悠悠 2023-09-27 17:11 81阅读 0赞

**目录**

一、题目描述

二、思路解析

三、题解代码

四、牛客链接

--------------------

## 一、题目描述 ##

> 小易来到了一条石板路前，每块石板上从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\]对应的步数

思路图解：

## ![6d2d0c7a203648eba618e88338082270.png][]       ##

## 三、题解代码 ##

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;
        }
    }

## 四、牛客链接 ##

[跳石板题目链接][Link 1]

[6d2d0c7a203648eba618e88338082270.png]: https://img-blog.csdnimg.cn/6d2d0c7a203648eba618e88338082270.png
[Link 1]: https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8?tpId=85&tqId=29852&tPage=2&rp=2&ru=/ta/2017test&qru=/ta/2017test/question-ranking