文章目录

1. 题目2. 解题思路2.1 递归2.2 记忆化递归2.2 动态规划 3. 代码实现3.1 递归3.2 记忆化递归3.2 动态规划 4. 总结5. 参考文献

1. 题目

题目一：求斐波那契数列的第n项。 写一个函数，输入n， 求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下：

数学公式：f(n) = f(n-1) + f(n-2)，n >=2

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

2. 解题思路

2.1 递归

直接按照数学公式，使用递归解决

缺点是重复计算了很多值。

2.2 记忆化递归

使用一个数组记录之前计算过的值，再次使用的时候直接中数组中取值而不再重复计算。

2.2 动态规划

第n个状态只与第n-1个状态和第n-2个状态相关，所以只需要用两个变量保存这两个值即可，在迭代的过程中不断地更新这两个值。

3. 代码实现

3.1 递归

class Solution: def fibonacci(self, n): """ """ # 基线条件 if n == 0: return 0 if n == 1: return 1 return self.fibonacci(n-1) + self.fibonacci(n-2)

但是，重复计算了很多，效率低。

3.2 记忆化递归

说白了，就是将之前递归计算出来值保存在一个数组中，下次用到这个值得时候就不用再重复计算了。

class Solution: records = [-1 for i in range(n+1)] # 记录计算的值 def fibonacci(self, n): if n == 0: return 0 if n == 1: return 1 if records[n] == -1: # 表明这个值没有算过 records[n] = fibonacci(n-1) +fibonacci(n-2) return records[n]

3.2 动态规划

只用两个变量保存n-1和n-2的值，就能得到n的值。

class Solution: def fibonacci(self, n): """ """ a, b = 0, 1 for i in range(n): a, b = b, a+b return a

4. 总结

动态规划对于目前的我来说还有点难度。需要继续加强学习。干吧地。

青蛙跳台阶的问题是类似的，跳第n步==第n-1步再跳1步或者第n-2步再跳两步，所以，f(n) = f(n-1) + f(n-2)，n>=2。

5. 参考文献

[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题