题目解析

方法一 暴力递归求解

This method is actually the use of recursive thinking to solve,Treat each number as a node of a binary tree,if and only if the leaf node of the binary tree is found（两个初始值0和1）时才结束循环,That is, the termination condition of the recursion.画图说明,如下：

It can be seen that the first calculationnFibonacci numbers of nodes,That is, the value of each node of the entire binary tree needs to be calculated,时间复杂度为2的n次方,非常庞大,代码见下.

方法二 Brute-force recursive optimization

How to reduce the time complexity in brute force recursive solution?？可以发现,The brute force recursion needs to calculate the value of each binary node in the above graph,But there are some values ​​that can be removed from the calculation,That is to say, the calculation of a large number of node values ​​is redundant..不难看出,when calculating the root node,Compute nodes are required4和节点3的值,But compute nodes4The value of , in turn, needs to be calculated by the node3和节点2的值,If the value of the left subtree is calculated,Then the value of the right subtree should not be solved recursively.,Therefore, only the value of the node in the left middle of the longest path in the graph needs to be calculated,The value of the root node can work out naturally.如下图,Just need to calculate the value on the red path：

sequential thinking,只需要计算n个斐波那契数,The time complexity can be reduced toO(n);
But how to get the value of each node？需要使用一个数组,to save the node value for each calculation,最多只有n个值,那么空间复杂度为O(n).

方法三 双指针思想

Although the method 2 to heavy recursive time complexity can be reduced toO(n), 但是空间复杂度也为O(n),How to reduce this space complexity?？Step by step to solve the element value of a certain position,and is obtained by some two values,类似这种问题,can be associated with the idea of ​​double pointers：
Slow pointer points to the leftmost end of the array,The fast pointer points to the array subscripted as1的位置,incrementally update the elements pointed to by two pointers,until the traversaln个元素为止,即可得到第n个斐波那契数,The time complexity at this time remains the sameO(n),And there are only two pointers in the space,doesn't use extra space,因此空间复杂度为O(1).

代码解析

1. 暴力递归

    public static int Fib1(int num) {
    
        if (num == 0) {
    
            return 0;
        }
        if (num == 1) {
    
            return 1;
        } else {
    
            return Fib1(num - 1) + Fib1(num - 2);
        }
    }

2. 去重递归

    public static int Fib2(int num) {
    
        int[] arr = new int[num + 1]; //初始化全为0的整型数组,Used to store the calculated at a timeFib数值,避免重复计算
        return resurse(arr, num);
    }

    private static int resurse(int[] arr, int nums) {
    
        if (nums == 0) {
    
            return 0;
        }
        if (nums == 1) {
    
            return 1;
        }
        if (arr[nums] != 0) {
     //如果该Fib数不为0Indicates that the value has been calculated before,直接进行返回,Use recursion only for values ​​that are only calculated the first time
            return arr[nums];
        }
        arr[nums] = resurse(arr, nums - 1) + resurse(arr, nums - 2);
        return arr[nums];
    }

注意：这里的arr数组初始化为全0的整数数组,Because the recursive solution is needed later when a certain Fibonacci number is calculated for the first time,否则,When a Fibonacci number is calculated,Array already existsarrat a location,This element is no longer0了.the next time the value is used,don't do the calculation again,直接返回该值即可.

3. 双指针求解

public static int Fib3(int num) {
    
        int low = 0, high = 1;
        if (num == 0) {
    
            return 0;
        }
        if (num == 1) {
    
            return 1;
        }
        for (int i = 2; i <= num; i++) {
    
            int sum = low + high;
            low = high;
            high = sum;
        }
        return high;
    }

定义两个指针：Pointer to an array subscript slow0,Fast pointer points to array subscript1,Same as above to set twodefaultThat is, the initial value of the two Fibonacci.从下标位置2开始循环,Add the last elements to get the current Fibonacci numbersum,update two pointers：The value pointed to by the fast pointer is assigned to the slow pointerlow,current Fibonacci numbersumAssigned to quick pointerhigh,do the next solution,Until the cycle to the firstnum个元素结束.Finally, return the fast pointer directlyhigh即可,lowPointers are stored on a Fibonacci number.