image.png
    方法一：暴力解法，时间复杂度O(2ⁿ)

    1. /**
    2.      * 暴力算法计算斐波那契数列第index位的值
    3.      * 递归计算
    4.      * @param index
    5.      * @return
    6.      */
    7.     public static int recursionCalculate(int index) {
    8.         if (index == 1) {
    9.             return 0;
    10.         }
    11.         if (index == 2) {
    12.             return 1;
    13.         }
    14.         return recursionCalculate(index - 1) + recursionCalculate(index -2);
    15.     }

    方法二：缓存部分已计算出的数据，时间复杂度O(n)，空间复杂度O(n)

        /**
     * 暴力算法进一步优化计算斐波那契数列第index位的值
     * 递归计算优化
     * @param index
     * @return
     */
    public static int recursionCalculateOptimization(int index) {
        if (index == 1) {
            return 0;
        }
        if (index == 2) {
            return 1;
        }
        // 定义一个数组，缓存已经计算的值
        int[] arr = new int[index];
        // 如果数组中存在，就直接返回，这个方法主要是减少递归方法 recursionCalculate(index - 2) 的重复计算
        if (arr[index-1] != 0) {
            return arr[index-1];
        }
        int result = recursionCalculate(index - 1) + recursionCalculate(index - 2);
        arr[index-1] = result;
        return result;
    }

    方法三：双指针，时间复杂度O(n)，空间复杂度O(1)

        public static int twoPointCalculate(int index) {
        if (index == 1) {
            return 0;
        }
        if (index == 2) {
            return 1;
        }
        int left = 0, right = 1, result;
        for (int i = 2; i < index; i++) {
            result = left + right;
            left = right;
            right = result;
        }
        return right;
    }