【数据结构和算法】跳台阶扩展问题

解法一

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

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

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

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