动态规划

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int Fibonacci(int n) {
        // write code here
        if(n<=2)
        {
            return 1;
        }
        int a=1; int b=1; int c=a+b;
        // 1 1
        for(int i=0;i<=n-3;i++)
        {
            c=a+b;
            a=b;
            b=c;

        }
        return c;
    
    }
};

递归法

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

递归法改进

• 用一个数组保存已经计算过的数字

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int arr[40]={0};
    
    int Fibonacci(int n) {
       if(n<=2)
       {
        arr[n-1]=1;
        return arr[n-1];
       }
        if(arr[n-1]!=0)
        {
            return arr[n-1];
        } 
        else
        {
            return arr[n-1]=Fibonacci(n-1)+Fibonacci(n-2);
        }
    
    }
};