解法一

这里的青蛙比前面两道题的青蛙更厉害一些,他一次可以跳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 casen等于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);
    }
}

我把部分算法题整理成了PDF文档,截止目前总共有1000多页,大家可以下载阅读

链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ 提取码:6666

如果觉得有用就给个赞吧,还可以关注我的微信公众号【数据结构和算法】查看更多的详细题解