[daily question 1] stone jumping -- dynamic programming

OJ link

Algorithmic thought ： The solution of this problem is that Xiao Yi should jump the slate at least several times , You can jump to the last slate . Then it is to solve the optimal solution of a stone jumping board , Then we will think of using dynamic programming to solve . In a nutshell Dynamic programming is the result of your solution at this step , Use the result of your last step .

Because in this question, you need to input the position of the stone slab where Xiaoyi is now , And the location of the stone slab that Xiaoyi will eventually reach . We define the original slate position as n, The final location is defined as m, Create a new array step, initialization step The content in is the maximum value of the shaping . So Xiaoyi's current position is step[n], Because Xiaoyi is going to the n The number of steps required for a slate is now 0, therefore step[n] = 0; stay step The array represents , What Xiaoyi wants step Subscript steps . The number of the next slate = The current slate number + Now a divisor of the slate number .

     //N = 4,M = 24：
    //4->6->8->12->18->24
    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();// Xiaoyi's initial position 
        int m = scanner.nextInt();// Where Xiaoyi will finally reach 
        int []step = new int[m + 1];
        // Create an array step, stay step Array , It stores the number of stone jumping boards , Here we initialize to the maximum value of an integer 
        for(int i = 0;i<step.length;i++){
    
            step[i] = Integer.MAX_VALUE;
        }
        step[n] = 0; // Xiao Yi in the first n A slate , To the first n A slate doesn't need to jump , So set step[n] = 
        for(int i = n;i<step.length;i++){
    
            if(step[i] == Integer.MAX_VALUE){
    
                continue;
            }
            List<Integer> list = div(i); // Get divisor 
            for(int j : list){
    
                if(i + j <= m && step[i + j] != Integer.MAX_VALUE){
    
                    step[i+j] = Math.min(step[i+j],step[i] + 1); // Because there are several ways to jump on a slate , Here, in order to get the optimal solution 
                    // So get the minimum number of steps to achieve the stone slab 
                }else if(i + j <= m){
     // The next slate to jump to = The current position of the slate + Now a divisor of the number of stone slabs , After finding the corresponding slate , Number of steps on the previous slate  + 1
                    step[i+j] = step[i] + 1;
                }
            }
        }
        if(step[m] == Integer.MAX_VALUE){
    
            System.out.println(-1);
        }else{
    
            System.out.println(step[m]);
        }
    }
    public static List<Integer> div(int n){
    
        List<Integer> list = new ArrayList<>();
        for(int i = 2;i * i <= n;i++){
    
            if(n % i == 0){
    
                list.add(i);
                if(n / i != i){
    
                    list.add(n / i);
                }
            }
        }
        return list;
    }