剑指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. 斐波那契数列算法时间复杂度