跳石板_跳台阶扩展问题

跳石板

跳石板

import java.util.*;
public class Main{
   public static ArrayList<Integer> findDivNumber(int N){
       ArrayList<Integer> div = new ArrayList<>();
       for(int i = 2;i*i<=N;i++){ //i*i <= N!!!
           if(N%i==0){
               div.add(i);
               if(i*i!=N){//避免重复添加!
                   div.add(N/i);
               }
           }
       }
       return div;
   }
   public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
       int N = sc.nextInt();
       int M = sc.nextInt();
       int count = 0;
       //初始状态:f(N) = 0 N 到达 N  0步 到达  
       //状态定义:到达 i 位置到达 i+j 最少步数!
       //转移方程: f(i+j) = Math.min(f(i+j),f(i)+1);
       //返回结果: f(M) 
       int[] dp = new int[M+1];
       for(int i = 0;i<= M;i++){
           //先初始化 为Integer.MAX_VALUE!
           dp[i] = Integer.MAX_VALUE;
       }
       dp[N] = 0;
       ArrayList<Integer> div = new ArrayList<>();
       for(int i = N; i<=M;i++){
           if(dp[i]==Integer.MAX_VALUE){
               //该石板不能走!
               continue;
           }
           //得到约数集!
           div = findDivNumber(i);
           for(Integer x : div){
               if((i+x)<=M&&dp[i+x]==Integer.MAX_VALUE){
                   //说明该位置还没有台阶可以到达,直接赋值到达i+x台阶最小次数!
                   dp[i+x] = dp[i] + 1;//到达当前位置台阶次数+1就可到达
               }else if((i+x)<=M){
                   //说明这里已经有了到达次数,判断是否为最小次数!
                   dp[i+x] = Math.min(dp[i+x],dp[i]+1);
               }
           }

       }
       if(dp[M]!=Integer.MAX_VALUE){
       System.out.println(dp[M]);
       }else{
       System.out.println(-1);    
       }
   }
}

细节:

1.有些位置不可跳跃!

2.防止数组越界!

跳台阶扩展问题

跳台阶扩展问题

链接：https://www.nowcoder.com/questionTerminal/953b74ca5c4d44bb91f39ac4ddea0fee?answerType=1&f=discussion
来源：牛客网

解法一

这里的青蛙比前面两道题的青蛙更厉害一些，他一次可以跳1阶，2阶，3阶……。所以要想跳到第n个台阶，我们可以从第1个台阶跳上来，也可以从第2个台阶跳上来……，所以递推公式是

f(n)=f(n-1)+f(n-2)+……+f(2)+f(1);

同样如果我们想跳到第n-1个台阶，也可以列出下面这个公式

f(n-1)=f(n-2)+……+f(2)+f(1);

通过这两个公式我们可以得出

f(n)=2*f(n-1)

实际上他是个等比数列，base case当n等于1的时候结果为1，来看下代码

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt() - 1;
        System.out.println(1 << num);
    }
}

解法二

import java.util.*;
public class Main{
    public static void main(String[] args){
         Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        //第x阶台阶的方法数: 2^(x-1) 
        int step = 1<<(x-1); //1左移 x-1位 就是 2^(x-1)
        System.out.println(step);
    }
}