递归---变态走楼梯（跳台阶进阶版）

/**
 * 案例 变态走楼梯
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
 * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
 *分析：走楼梯的进阶版，之前是每一步只能有2种走法，现在是每一步有n种走法。同样来寻找规律。
 * 同样，n=1时，走法=1；n=2时，走法=2；
 * n=3时情况就和之前不同了 我们画图分析
 * 假设有三级台阶，则可以一次走1级或一次走2级或一次走3级，如果一次走1级则还剩2级台阶，产生2种走法
 * （上面已经说了），一次走2级则还剩1级只有一种走法，一次走三级就全部走完了，只有1种走法。
 * 总共的走法就是2+1+1=4.
 * n                      3
 *                      / |  \
 * 第一步走完剩余级数    2  1  0
 * 走法                 2  1  1
 *
 * 归纳出公式就是 f(3)=f(3-1)+f(3-2)+f(3-3)=f(2)+f(1)+f(0)
 *
 * 同样，分析n=4时的情况,第一次可以走1步或走2步或走3步或走4步，这样产生的剩余台阶数分别为3，2，1，0；
 * 我们发现这是一个递归，当剩余台阶数为3，2，1，0时的情况上述都已经分析。
 * n                              4
 *                             / | \ \
 * 第一步走完剩余级数           3 2  1 0
 *走法                        4  2  1  1
 * 归纳出公式就是 f(4)=f(4-1)+f(4-2)+f(4-3)+f(4-4)=f(3)+f(2)+f(1)+f(0)
 * 因此得到递推公式 f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=f(n-1)+f(n-2)+...+f(1)+(0)
 * 采用数学归纳法推导：
 * f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=f(n-1)+f(n-2)+...+f(1)+(0)   ----- 1
 * f(n-1)=f(n-2)+f(n-3)+...+f(1)+f(0)                                    ----- 2
 * ...
 * 全部带入1式，得到f(n)=2f(n-1) n>=2 如果这里看的不太明白的建议复习一下高中数学数列部分知识！
 * 所以 f(n) =  1      n=0
 *              1      n=1
 *             2f(n-1) n>=2
 * **/

public class zoulouti2 {
    public static void main(String[] args){
        int result = solution(3);
        System.out.println(result);
    }
    static int solution(int n){
        if (n==0) return 1;
        if (n==1) return 1;
        return 2*solution(n-1);
    }
}