题目描述

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

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

样例

输入整数 n=5 

返回 5

算法1

动态规划入门题目
状态转移
dp[n] = dp[n-1] + dp[n-2]
使用全局变量避免重复计算

C++ 代码

class Solution {
public:
    int v[100000] = { 0 };

    int Fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n ==2) {
            v[n] = 1;
            return v[n];
        }
        if (v[n] != 0) return v[n];
        for (int i = 3; i <= n; i++) {
            v[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
        }

        return v[n];
    }
};