2020年10月22日 斐波那契数列

**

题目描述

** 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。 n<=39

自己的分析

利用arraylist的add和get函数实现，方法简单

import java.util.ArrayList; public class Solution { public int Fibonacci(int n) { ArrayList<Integer> list = new ArrayList<>(); list.add(0); list.add(1); if(n==0){ return 0; } if(n==1){ return 1; } int i = 1; while(i!=n){ list.add(list.get(i)+list.get(i-1)); i++; } return list.get(i); } }

但是实际上这个题目有多种解法 递归，记忆化搜索，动态规划和动态规划的空间优化。

方法一：递归 题目分析，斐波那契数列公式为：f[n] = f[n-1] + f[n-2], 初始值f[0]=0, f[1]=1，目标求f[n] 看到公式很亲切，代码秒秒钟写完。

public class Solution { public int Fibonacci(int n) { if(n==0||n==1){ return n; } return Fibonacci(n-1)+Fibonacci(n-2); } }

优点，代码简单好写，缺点：慢，会超时 时间复杂度：O(2^n) 空间复杂度：递归栈的空间 ###方法二：记忆化搜索 拿求f[5] 举例

---

动态规划

但是如果想让空间继续优化，那就用动态规划，优化掉递归栈空间。 动态规划不同的是，不用递归的过程，直接从子树求得答案。过程是从下往上。

public class Solution { public int Fibonacci(int n) { int[] fi = new int[n+2]; fi[0]=0; fi[1]=1; for(int i = 2;i<=n;i++){ fi[i] = fi[i-1] + fi[i-2]; } return fi[n]; } }