使用js实现变态跳台阶

Question

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

Answer 1

首先本题可以使用计算机里的递归进行解决，但是时间复杂度及其高。在这里我站在数学的角度将其通解求出，仅仅只需O(1)的时间复杂度即可完美解决。
此题严格来说应该属于一道数学题，答案为2的n-1次方。
可以用两种不同的数学思考角度进行解题。
方法一：数列（函数）的递归公式（同样可以理解为动态规划里的状态转移方程）
从1级台阶上到n级台阶可以拆分为，先上1个台阶然后再上到n级台阶加上从2级台阶上到n级台阶。
先上1个台阶然后再上到n级台阶与从1级台阶上到n-1级台阶是完全一致的，并且从2级台阶上到n级台阶与从1级台阶上到n-1级台阶也是完全一致的。这里具体细节不太好描述，大家可以自己再细细的意会意会。
综上所述，函数的递推公式为f(n)=f(n-1)+f(n-1)=2f(n-1)，即f(n)=2的n-1次方。
方法二：排列组合原理
宏观来看，想要从1级台阶跳到n级台阶，总共有n个台阶，由于第n级台阶是必须要到达，所以只有一种选择性，而从1级台阶到n-1级台阶这总共n-1个台阶都有两种选择性，即经过与没经过，所以将所有可能性进行组合累乘，结果即为f(n)=2的n-1次方。