剑指Offer 10. 斐波那契数列

本篇文章的几个题目都可以看做是斐波那契问题。

斐波那契数列

题目

求斐波那契数列的第 n 项

解法1[Java]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int Fibonacci(int n) {
if (n <= 1) return n;

int pre2 = 0, pre1 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = pre2 + pre1;
pre2 = pre1;
pre1 = fib;
}
return fib;
}
}

时间复杂度为 $O(n)​$,空间复杂度为 $O(1)​$。

解法2[Java]:打表

把每一步的结果计算出来,最后直接根据序号返回对应值。

优点:打出来的表可复用。缺点:空间复杂度为 $O(n)$。

跳台阶问题

这也看作一个斐波那契问题。

题目

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

解答1[Java]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int JumpFloor(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 2; i < n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
}

从 $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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int RectCover(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}

return result;
}
}

$2 \times 8$ (2行8列)的矩形,

①最左边竖着放,右边变成 $2 \times 7$ 的问题。

②最左边横着放,要放两个,右边变成 $2 \times 6$ 的问题。

变态跳台阶问题

参考资料

  1. 对斐波那契问题分析的非常好的一篇文章:计算斐波纳契数,分析算法复杂度
  2. 斐波那契数列算法时间复杂度