本文共 1330 字，大约阅读时间需要 4 分钟。

#剑指offer Day3 一类 “ 斐波那契 ”问题

1. 思路

斐波那契（Fibonacci）数列是经典的递归问题。可由下式表示：

2. 相关题目

1. 第8题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

   分析：对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，所以 F(n) = F(n-1) + F(n-2)，这正是本文所说类型。

   最暴躁的解法：自底向上    int FrogJumping(int n){    if(n < 0) return -1;    if(n == 0 || n == 1 || n == 2)  return n;    return FrogJumping(n - 1) + FrogJumping(n - 2);}    // 若n很大，递归程度很深，容易爆栈。迭代求解：自顶向下int jumpFloor(int number) {        int t1 = 1, t2 = 2, total = 0;        if (number == 1 || number == 2) return number;        for(int i = 3;i <= number;i++) {            total = t1 + t2;            t1 = t2;            t2 = total;        }        return total;    }

2. 第 9 题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

   分析：每个台阶可以看作一块木板，让青蛙跳上去，n个台阶就有n块木板，最后一块木板是青蛙到达的位子，必须存在，其他 (n-1) 块木板可以任意选择是否存在，则每个木板有存在和不存在两种选择，(n-1) 块木板就有 [2^(n-1)] 种跳法，可以直接得到结果。

   int jumpFloor(int number) {        if (number == 1 || number == 2) return number;        return 2 * jumpFloor(number - 1);    }

3. 第10题：我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？

   比如n=3时，2*3的矩形块有3种覆盖方法：

   

   分析：

   

   所以还是斐波那契数列，和上面的青蛙跳台阶是一样的编程思路。

转载地址：http://mmwki.baihongyu.com/