本文共 1745 字，大约阅读时间需要 5 分钟。

链接：

题目描述

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

分析：

假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)；假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)；假定第一次跳的是3阶，那么剩下的是n-3个台阶，跳法是f(n-3)......假定第一次跳的是n-1阶，那么剩下的是1个台阶，跳法是f(1)； 假定第一次跳的是n阶，那么剩下的是0个台阶，跳法是1种；

则：

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

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

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

f(n)/f(n-1) = 2

f(n) = 2^(n-1)

#递归class Solution:    def jumpFloorII(self, number):        if number <= 0:            return 0        else:            return pow(2,number-1)

二、青蛙跳台阶问题，一只青蛙要跳上n层高的台阶，一次能跳一级，也可以跳两级，请问这只青蛙有多少种跳上这个n层高台阶的方法？

（1）递归

设青蛙跳上n级台阶有f(n)种方法，把这n种方法分为两大类，第一种最后一次跳了一级台阶，这类方法共有f(n-1)种，第二种最后一次跳了两级台阶，这种方法共有f(n-2)种，则得出递推公式f(n)=f(n-1)+f(n-2)

class Solution:    def climbStairs(self, n):        if n==1:            return 1        elif n==2:            return 2        else:            return self.climbStairs(n-1)+self.climbStairs(n-2)

（2）用循环来代替递归

class Solution:    def climbStairs(self, n):        if n==1 or n==2:            return n        a=1;b=2;c=3        for i in range(3,n+1):            c=a+b;a=b;b=c        return cclass Solution:    def jumpFloor(self, number):        if number == 1:            return 1        elif number == 2:            return 2        f1 = 1        f2 = 2        for i in range(2,number-1):            f1,f2 = f2,f1+f2        return f1+f2

（3）建立简单数学模型，利用组合数公式

设青蛙跳上这n级台阶一共跳了z次，其中有x次是一次跳了两级，y次是一次跳了一级，则有z=x+y ,2x+y=n,对一个固定的x，利用组合可求出跳上这n级台阶的方法共有

种方法

class Solution:    def climbStairs(self, n):        def fact(n):            result=1            for i in range(1,n+1):                result*=i            return result        total=0        for i in range(n/2+1):            total+=fact(i+n-2*i)/fact(i)/fact(n-2*i)        return total

转载地址：http://myfab.baihongyu.com/