法。如果有2级台阶，那就有两种跳法： 一种是分两次跳，每次跳1级；
我们把n级台阶时的跳法看成n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：
一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1);
二是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。
因此，n级台阶的不同跳法的总数如f(n)=f(n-1)+f(n-2)。
在青蛙跳台阶的问题中，如果把条件改成：
一只青蛙一次可以跳上1级台阶，也可以跳上2级… …它也可以跳上n级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
当只有一级台阶时，只有一种情况，跳一级。f(1)=1;
当有两级台阶时，可以跳一级跳两次，也可以直接跳两级。f(2)=2;
当有三级台阶时，第一步可以分三种方法跳：
1、第一步跳一级，后面按2级台阶算，记f(2)。
2、第一步跳两级，后面按一级台阶算，记f(1)。
3、第一步跳三级，直接跳完。
所以总共为：f(2)+f(1)+1=4;
当有四级台阶时，第一步分四种跳法：
2、第一步跳两级，后面按两级台阶算，记f(2)。
4、第一步跳四级，直接跳完。
所以总共为：f(3)+f(2)+f(1)+1=8；
以上，我们用数学归纳法可以证明f(n)=2的n-1次方。
代码：乘法求阶层：
以上为剑指offer青蛙跳台阶部分题目。
本站由以下主机服务商提供服务支持：