斐波那契数列相关问题

---

题目 1：求斐波那契数列的第 n 项

---

代码实现：

public class Fibonacci {

    /**
     * 解法 1：递归
     *
     * 优点：代码简洁
     * 缺点：效率不高
     *
     * @param n
     * @return
     */
    private static int fibonacci(int n) {
        if (n <= 1)
            return n;
        int[] fib = new int[n + 1];
        fib[1] = 1;
        for (int i = 2; i <= n; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
        return fib[n];
    }

    /**
     * 解法 2：将递归的算法用循环实现 (自下而上计算, 根据f(0)、f(1)算出f(2)...)
     *
     * 优点：提高了时间效率
     *
     * 时间复杂度：O(n)
     *
     * @param n
     * @return
     */
    private static int fibonacci2(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;
    }

    public static void main(String[] args) {
        System.out.print("输入要求斐波那契数列的项数：");
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();

        int result1 = fibonacci(n);
        System.out.print("递归的方式：" + result1);
        System.out.println();
        int result2 = fibonacci2(n);
        System.out.print("以循环的方式实现递归：" + result2);
    }
}

---

两种解法的比较：

递归：

优点：代码简洁

缺点：

• 但由于递归是调用函数自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间；
• 调用栈溢出。每一次函数调用时都需要在内存栈中分配内存空间，而每个内存栈的容量有限，所以，当递归调用的层级太多时，就会超出栈的容量，导致调用栈溢出。

循环的方式实现递归：

优点：提高了时间效率。自下向上计算每一项的值，先根据 f(0)、f(1) 计算 f(2) 的值，再根据 f(1) 、f(2) 计算 f(3)的值...以此类推就可以求得第 n 项的值了。时间复杂度为 O(n)

---

题目 2 ：青蛙跳台阶问题

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

---

分析：

• 当 n 为 1 时，只有 1 种跳法；
• 当 n 为 2 时，有 2 种跳法；
• 当 n > 2 时，f(n) = f(n - 1) + f(n - 2)

---

代码实现：

/**
     * 青蛙跳台阶问题
     * @param n
     * @return
     */
    private static long jumpFloor(int n) {
        if (n <= 2) {
            return n;
        }

        long pre2 = 1;
        long pre1 = 2;
        long result = 1;
        for (int i = 2;i < n; i++) {
            result = pre2 + pre1;
            pre2 = pre1;
            pre1 = result;
        }
        return result;
    }

---

题目 3 ：青蛙跳台阶问题升级版

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶...也可以跳上 n 级台阶，此时该青蛙跳上 n 级台阶总共有多少种跳法？

---

思路：f ( n ) 为 n 级台阶时青蛙的跳法

f ( 1 ) = 1

f ( 2 ) = f ( 2- 1 ) + f ( 2 - 2 )

f ( 3 ) = f ( 3 - 1 ) + f ( 3 - 2 ) + f ( 3 - 3 )

...

f ( n ) = f ( n - 1 ) + f ( n - 2 ) + f ( n - 3 ) + ... + f ( n - n ) = f ( 0 ) + f ( 1 ) + ... + f ( n - 2 ) + f ( n - 1 )

= 2 ^ 1 * f ( n -1 ) = 2 ^ 2 * f ( n - 2 ) = ... = 2 ^ ( n -1 ) * f ( 1 ) = 2 ^ ( n -1 )

---

代码实现：

/**
     * 青蛙跳台阶问题升级版  f(n) = 2 ^(n - 1)
     * @param n
     * @return
     */
    private static long jumpFloorUpgrade(int n) {
        long[] solutions = new long[n];

        Arrays.fill(solutions, 1);  // 初始化 solutions

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                solutions[i] += solutions[j];
            }
            System.out.print(solutions[i] + " ");
        }

        return solutions[n - 1];
    }

 /**
     * f(n) = 2 * f(n - 1)
     * @param n
     * @return
     */
private static long jumpFloorUpgrade1(int n) {
        if (n <= 1) {
            return n;
        }

        return 2 * jumpFloorUpgrade1(n - 1);
    }

---

题目 4 ：矩形覆盖问题 (类似青蛙跳台阶问题)

用 2 x 1 的小矩形横着或竖着去覆盖更大的矩形。比如说，用 8 个 2 x 1 的小矩形无重叠的覆盖一个 2 x 8 的大矩形，总共有多少种方法？

---

思路：小矩形横着放在大矩形中占 2 列，竖着放 占 1 列，所以自然而然就归结为斐波那契数列问题了

---

代码实现：

private static long coverRectangle(int n) {
        if (n <= 2) {
            return n;
        }

        long pre2 = 1;
        long pre1 = 2;
        long result = 1;
        for (int i = 3;i <= n; i++) {
            result = pre2 + pre1;
            pre2 = pre1;
            pre1 = result;
        }
        return result;
    }