牛客网——跳台阶和变态跳台阶问题

一、跳台阶spa

题目描述：一只青蛙一次能够跳上1级台阶，也能够跳上2级。求该青蛙跳上一个n级的台阶总共有多少种方法？blog

解答：这种问题通常是有规律的，跳1级台阶，只有1种方法；跳2级台阶，有2种方法；跳2级台阶，有3种方法；跳4级台阶，有5种方法，依次下去，跳一个n级的台阶的方法数是跳n-1级台阶的方法数与跳n-2阶台阶的方法数的总和。这种思路能够用逆推去想，要跳上一个n级台阶，能够从n-1级台阶跳1级，也能够从n-2级台阶跳2级，这就至关于跳上n-1级台阶的方法加上跳上n-2级台阶的方法。递归

注意：这个问题的规律和斐波拉契数列是同样的。程序

程序实现：方法

（1）递归方法：时间复杂度随输入规模呈指数级增加。im

（2）迭代方法：时间复杂度为 O(n)img

二、变态跳台阶时间

题目描述：一只青蛙一次能够跳上1级台阶，也能够跳上2级，。。。，它也能够跳上n级，求该青蛙跳上一个n级的台阶总共有多少种方法？co

解答：也能够用逆推的思路去想，跳n级台阶，能够从n-1级跳上来，也能够从n-2级跳上来，从n-3级跳上来，依次下去，从第1级跳上去，或直接跳上去，因此，跳n级台阶的方法数至关于其它全部台阶数的方法的总和再加上从0级跳上去，表达式为 f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + 1。例如：ps

当跳1级台阶时，f(1) = 1;

当跳2级台阶时，f(2) = f(1) + 1 = 2;

当跳3级台阶时，f(3) = f(2) + f(1) + 1 = 4;

当跳4级台阶时，f(4) = f(3) + f(2) + f(1) + 1 = 8;

。。。。。。。。。。。。。。。。。。。。。

f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + 1

f(n-1) = f(n-2) +...+ f(2) + f(1) + 1

===》》 f(n) - f(n-1) = f(n-1)     ===》》f(n) = 2 * f(n-1)

程序实现：

（1）递归法：

（2）迭代法：