题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

样例

输入整数 n=5 

返回 5

算法1

(直接递归)

Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2);

C++ 代码

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

算法2

(剪枝递归)

用一个数组num存结果。

C++ 代码

int num[50];
class Solution {
public:
    int Fibonacci(int n) {
        if(n==0) return 0;
        if(n==1 || n==2) return 1;
        if(!num[n]) num[n]=Fibonacci(n-1)+Fibonacci(n-2);
        return num[n];
    }
};