【剑指 Offer 10- I. 斐波那契数列】

package com.example.demomain.demoleetcode.easy;

import org.junit.jupiter.api.Test;

public class Fib {
    /**
     * 1、递归法：超时。。。
     * 

     * 原理： 把 f(n)f(n) 问题的计算拆分成 f(n−1) 和 f(n−2) 两个子问题的计算，并递归，
     * 以 f(0) 和 f(1) 为终止条件。
     * 缺点： 大量重复的递归计算，例如 f(n) 和 f(n−1) 两者向下递归需要 各自计算 f(n−2) 的值。
     *
     * @param n
     * @return
     */
    public int fibRecursiveCall(int n) {
        if (n == 0 || n == 1 || n == 2) {
            return n == 0 ? 0 : 1;
        }
        return fibRecursiveCall(n - 1) + fibRecursiveCall(n - 2);
    }

    /**
     * 2、记忆化递归法：
     * 

     * 原理： 在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n) 的数字值，
     * 重复遇到某数字则直接从数组取用，避免了重复的递归计算。
     * 缺点： 记忆化存储需要使用 O(N) 的额外空间。
     *
     * @param n
     * @return
     */
    public int fibRecursiveCallMemory(int n) {
        if (n <= 1) {
            return n;
        }
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            // 初始化为 -1
            f[i] = -1;
        }
        return fibRecursiveCallMemory(n, f);
    }

    public static int fibRecursiveCallMemory(int n, int[] f) {
        if (n <= 1) {
            // 0 、1
            return f[n];
        }
        if (f[n] != -1) {
            // 已在数组中缓存过
            return f[n];
        } else {
            // 未在数组中缓存过，缓存 当前值 : 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
            f[n] = (fibRecursiveCallMemory(n - 1, f) + fibRecursiveCallMemory(n - 2, f)) % 1000000007;
        }
        return f[n];
    }


    /**
     * 3、动态规划
     * 原理： 以斐波那契数列性质 f(n+1)=f(n)+f(n−1)f(n+1)=f(n)+f(n−1) 为转移方程。
     *
     * @param n
     * @return
     */
    public int fibdp(int n) {
        int a = 0, b = 1, sum;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

    @Test
    public void testFib() {
        int n = 3;
        //System.out.println(fibRecursiveCall(n));
        System.out.println(fibRecursiveCallMemory(n));
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88