跳石板_跳台阶
跳石板
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); } }#笔试题#