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

解法一

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