剑指Offer 10. 斐波那契数列
本篇文章的几个题目都可以看做是斐波那契问题。
斐波那契数列
题目
求斐波那契数列的第 n 项
解法1[Java]:
1 | public class Solution { |
时间复杂度为 $O(n)$,空间复杂度为 $O(1)$。
解法2[Java]:打表
把每一步的结果计算出来,最后直接根据序号返回对应值。
优点:打出来的表可复用。缺点:空间复杂度为 $O(n)$。
跳台阶问题
这也看作一个斐波那契问题。
题目
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
解答1[Java]:
1 | public class Solution { |
从 $n>2$ 开始,所以跳法可以分为两类
①第一下跳一级,这个时候剩下的跳法就是 $f(n-1)$,
②第一下跳两级,这个时候剩下的跳法就是 $f(n-2)$,
所以,$f(n)=f(n-1)+f(n-2),n>2$。
注意:每一类跳法的总数是第一下的跳法乘以剩下的跳法,不是相加。
矩形覆盖问题
题目
我们可以用 $2 \times 1$ 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 $2 \times 1$ 的小矩形无重叠地覆盖一个 $2 \times n$ 的大矩形,总共有多少种方法?
解答1[Java]:
1 | public class Solution { |
$2 \times 8$ (2行8列)的矩形,
①最左边竖着放,右边变成 $2 \times 7$ 的问题。
②最左边横着放,要放两个,右边变成 $2 \times 6$ 的问题。
变态跳台阶问题
参考资料
- 对斐波那契问题分析的非常好的一篇文章:计算斐波纳契数,分析算法复杂度
- 斐波那契数列算法时间复杂度