package dynamic;

/**
 * 题目:斐波那契数列
 * 求斐波那契数列的第 n 项,n <= 39。
 *
 * @Author Gavin
 * @date 2022年05月02日 23:00
 */
public class solution_11 {
 //Time:O(n),Space:O(n)
 public int solution_1(int n) {
 if (n <= 1)
 return n;
 int[] fib = new int[n + 1];
 fib[1] = 1;
 for (int i = 2; i <= n; i++)
 fib[i] = fib[i - 1] + fib[i - 2];
 return fib[n];
 }
 //Time:O(n),Space:O(1)
 public int solution_2(int n) {
 if (n <= 1)
 return n;
 //由于只关注前一个和前两个数的值,所以可以直接使用两个变量就可以了。
 int pre2 = 0, pre1 = 1;
 int fib = 0;
 for (int i = 2; i <= n; i++) {
 fib = pre2 + pre1;
 pre2 = pre1;
 pre1 = fib;
 }
 return fib;
 }

 //题目的要求是n<39,所以可以初始化的时候就计算好,这样在获取的时候就可以O(1)时间获取
 private int[] fib = new int[40];
 public solution_11() {
 fib[1] = 1;
 for (int i = 2; i < fib.length; i++)
 fib[i] = fib[i - 1] + fib[i - 2];
 }
 public int solution_3(int n) {
 return fib[n];
 }
}