变态跳台阶 ​

题目： ​

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

思路： ​

变态跳台阶的问题同上一个问题的思考方案是一样的，我们可以得到一个结论是，每一项的值都等于前面所有项的值的和。

• f(1) = 1
• f(2) = f(2-1) + f(2-2) //f(2-2) 表示 2 阶一次跳 2 阶的次数。
• f(3) = f(3-1) + f(3-2) + f(3-3)
• ...
• f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

再次总结可得

        | 1 ,(n=0 )
f(n) =  | 1 ,(n=1 )
        | 2\*f(n-1),(n>=2)