青蛙爬台阶问题的几种解法

-在办公室认真工作（聊微信）boss突然进来给了这么一道题要考验一下我学习python的程度

---

题目描述

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

简单说就是有一只青蛙每次只能跳一到两级台阶，在一个给定的台阶数下这只青蛙有多少种达到顶端的方法。

思路分析

这里用了两种方法实现，并用python代码实现。

方法一 ：递归

看到题目第一个想法就是递归，假设青蛙跳上n级台阶有f(n)种可能的方法，可以分成两大类情况。第一种是最后一次跳了一级台阶，共有f(n-1)种，第二种是最后一次跳了两级台阶，这种方法共有f(n-2)种。得出递推公式f(n)=f(n-1)+f(n-2),其中，f(1)=1,f(2)=2。代码如下：

def jump_frog(n): if n == 1: return 1 elif n == 2: return 2 else: return jump_frog(n-1) + jump_frog(n-2)

嗯，boss看了一眼，你运行个n=40给我看下。我一想事情可能没那么简单，在经过了十多秒的沉默后结果才出来。yeah，递归真的很慢诶，数量级高的情况下时间真的爆炸。try to do it better……

方法二 ：循环代替递归

使用循环代替递归，效率真的很高。代码如下：

#儿童写法 def jump_frog(n): a = 1 b = 2 if n == 1 or n ==2: return n for i in range(3,n+1): c = a + b a = b b = c return c #成年人写法 def jump_frog(n): assert n >= 0 #n不能为负数 if n in [0, 1]: return 1 else: a, b = 1, 1 for i in range(2, n + 1): a, b = b, a + b return b

perfect～ boss嘿嘿一笑，你知道怎么让第一个递归变快吗？看我的

from functools import lru_cache @lru_cache(maxsize=None) def jump_frog(n): if n == 1: return 1 elif n == 2: return 2 else: return jump_frog(n-1) + jump_frog(n-2)

what?这是什么东东。boss嘿嘿一笑拂袖而去，google一下。原来functools这个模块中，有lru_cache这个一个神奇的装饰器存在。functools.lru_cache的作用主要是用来做缓存，他能把相对耗时的函数结果进行保存，避免传入相同的参数重复计算。同时，缓存并不会无限增长，不用的缓存会被释放。一篇解释不错的文章[https://blog.csdn.net/wzqnls/article/details/78506022]

心得：多思考多写代码多优化。