一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶.求该青蛙跳上一个 n 级的台阶总共有多少种跳法.
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1.
设跳上 n 级台阶有 f(n) 种跳法.在所有跳法中,青蛙的最后一步只有两种情况: 跳上 1 级或 2 级台阶.
f(n) 为以上两种情况之和,即 f(n)=f(n-1)+f(n-2) ,以上递推性质为斐波那契数列.本题可转化为 求斐波那契数列第 n 项的值.与 面试题10- I. 斐波那契数列 等价,唯一的不同在于起始数字不同.
本题如果使用递归实现,时间会超限,因此使用循环.
空间复杂度:O(1) ,几个标志变量使用常数大小的额外空间.