题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路:如果只有一级台阶,则只有一种跳法(1);如果有两级台阶,则有两种跳法:(1,1;2);如果有三级台阶,则有三种跳法:(1,1,1;1,2;2,1);如果有四级台阶,则有五种跳法:(1,1,1,1;1,1,2;1,2,1;2,1,1;2,2;)......依次类推可以发现如下规律:
当n=1,f(n)=1;
当n=2,f(n)=2;
当n>=3,f(n)=f(n-1)+f(n-2);
可以采用两种方法,一种是用递归,另一种是迭代。
实现代码:
迭代方法:
第二个方法为递归。递归比迭代运行时间要更久一点。