斐波那契数列

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

假定从 0 开始，第 0 项为 0。

数据范围
0 ≤ n ≤ 39

样例

输入

5

输出

5

题解

斐波那契数列 f(0) = 0, f(1) = 1; 当 n >= 2 时 f(i) = f(i - 1) + f(i - 2); 定义个数组, 长度为n + 1; 如果 n <= 1 返回 n; f[0] = 0, f[1] = 1; 从2开始迭代f[i] = f[i - 1] + f[i + 1], 返回f[n]即可。

class Solution {
    int[] dp = new int [40];
    public int dfs(int x) {
        if (dp[x] != -1) return dp[x];
        return dp[x] = dfs(x - 1) + dfs(x - 2);
    }
    
    public int Fibonacci(int n) {
        for (int i = 0; i <= n; i ++) {
            dp[i] = -1;
        }
        dp[0] = 0; dp[1] = 1;
        return dfs(n);
    }
}