题目描述

以 O(1) 的时间复杂度求菲波那切数列。

解题思路

如果使用递归求解，那么会重复计算一些子问题。例如，求 f(10) 需要计算 f(9) 和 f(8)，计算 f(9) 需要计算 f(8) 和 f(7)，可以看到 f(8) 被重复计算了。

递归方法是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，避免重复求解子问题。

public class Solution {
    private int[] fib = new int[40];
    public Solution() {
        fib[1] = 1;
        fib[2] = 2;
        for(int i = 2; i < fib.length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
    public int Fibonacci(int n) {
        return fib[n];
    }
}