剑指offer的题目（Java实现）

一、简单概念解析

1.1 斐波那契数列–数组

描述：

当前需要用户提供一个整数n，要求计算并返回斐波那契数列中的第n项，其中数列的起始项为第0项，其值为0，第1项的值为1。所输入的整数n应满足不超过39的条件。

①递归

分析：

斐波那契数列的表达式为：F(1)=1，F(2)=1，且对于n≥3且n为正整数的情况，F(n)=F(n-1)+F(n-2)。

    public class Solution {
    public int Fibonacci(int n) {
        if(n <= 1){
            return n;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
    }
    
    
      
      
      
      
      
      
      
      
    

复杂度分析：

在时间复杂度方面，该算法的计算量呈现指数级增长，具体表现为O（2^n）的形式。
就空间复杂度而言，其占用的存储资源保持恒定，数值为O（1）。

递归优化策略

递归算法在执行过程中会导致大量重复数据的计算，为避免这一问题，可以采用数组来存储已