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

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

问题描述

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

解题思路

n=1（只有1级台阶时） ： 只有1种跳法
n=2（只有2级台阶时）：有2种跳法，可以跳2个1级的台阶，也可以直接跳2级台阶
n=3（只有3级台阶时）：分为两种情况：最后是跳1级台阶到顶，此时前面还剩2级台阶，变为了n=2的情况（有2种跳法）；最后是跳2级台阶到顶，此时前面还剩1级台阶，变为了n=1的情况（有1种跳法）。所以一共有2+1=3种跳法。
n=4（只有4级台阶时）： 分为两种情况：最后是跳1级台阶到顶，此时前面还剩3级台阶，变为了n=3的情况（有3种跳法）；最后是跳2级台阶到顶，此时前面还剩2级台阶，变为了n=2的情况（有2种跳法）。所以一共有3+2=5种跳法。

所以是一个类似斐波那契数列，f(n) = f(n-1) + f(n-2)

def fib(n):a, b = 0, 1for _ in xrange(n):a, b = b, a + breturn b

类似的问题还有一个：

问题描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，
总共有多少种方法？

解题思路

n=1：只有竖放1个矩形一种解决办法
n=2：有横放2个矩形，竖放2个矩形两种解决办法
n=3：n=2的基础上加1个竖向，n=1的基础上加2个竖向
n=4：n=3的基础上加1个竖向，n=2的基础上加2个竖向
·
·
f(n) = f(n-1) + f(n-2)

斐波那契数列变种。。。。。

这种问题，可以通过从n=0或1开始慢慢先算几个，来找出相邻两个数或相邻的几个数之间的关系。