《剑指offer》 递归和循环第三题:变态跳台阶

题目描述:

??一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路:??

? ? ? ?青蛙有两种选择：跳一级或者跳两级。如果跳一级，则还剩下n-1级台阶需要跳，这时青蛙又面临着跳一级或者跳两级的选择；如果跳两级，则还剩下n-2级台阶需要跳，这时青蛙又面临着跳一级或者跳两级的选择。以此类推，每次跳跃青蛙都有两种选择，一直到最后一步跳上第n级台阶。即青蛙跳上n级台阶的总跳法数可以表示为：f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + f(0)

就是2*f(n-1)。

青蛙第一次选择跳一级台阶，那么剩下的n-1级台阶就变成了一个子问题，即求解青蛙跳上n-1级台阶的总跳法数。同样地，对于n-1级台阶，青蛙在每一级台阶上也有两种选择：跳或不跳。???????

这也是与上一题跳台阶不同的地方

?代码实现：

 public int solution(int n)
    {
        if(n==0||n==1||n==2)
            return n;

        return 2*solution(n-1);
    }

测试类：

 public static void main(String[] args) {
        Reverse3 reverse=new Reverse3();
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(reverse.solution(n));
    }

测试结果：