跳石板_跳台阶

跳石板

跳石板

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