题目描述
以 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];
}
}
