剑指offer010 斐波那契数列

Problem:

求斐波那契数列的第 n 项，n <= 39。

Intuition:

斐波那契数列很适合使用动态规划来求解,它在数学上是使用递归来定义的,公式为F(n) = F(n-1) + F(n-2).
使用动态规划来将重复计算的结果具有”记忆性”,就可以将时间复杂度降低为O(n).

Solution:

public class Solution {

    private int[] fib = new int[40];

    public Solution() {
    	fib[0]=1;
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
    }

    public int Fibonacci(int n) {
        return fib[n];
    }
}