2021/1/18 斐波那契数列

1 解题思路

1. 声明定义一个由-1填充的数组arr，在索引为n的地方存储f(n)，-1表示尚未存储数据；
2. 若n = 0或1，直接返回n本身；
3. 若不满足2，判断arr[n]若不是-1，说明已经存储过f(n)，不需要再进行计算，直接返回arr[n]；
4. 若不满足3，进行计算f(n) = f(n - 1) + f(n - 2)，并在arr[n]存储f(n)结果；

2 Java代码实现

public class Solution {
    public int Fibonacci(int n) {
        // 1. 声明定义一个由-1填充的数组arr，在索引为n的地方存储f(n)，-1表示尚未存储数据；
        int[] arr = new int[128];
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = -1;
        }
        return fib(arr, n);
    }

    private int fib(int[] arr, int n) {
        // 2. 若n = 0 或 1，直接返回n本身；
        if (n == 0 || n == 1) return n;
        // 3. 若不满足2，判断arr[n]若不是-1，说明已经存储过f(n)，不需要再进行计算，直接返回arr[n]；
        if (arr[n] != -1) {
            return arr[n];
        } else {
        // 4. 若不满足3，进行计算f(n) = f(n - 1) + f(n - 2)，并在arr[n]存储f(n)结果；
            int result = fib(arr, n - 1) + fib(arr, n - 2);
            arr[n] = result;
            return result;
        }
    }
}