题目描述
求斐波那契数列的第n项，n <=39。
解题思路
如果使用递归求解，会重复计算一些子问题。例如，计算f（4）需要计算f(3)和f(2)，计算f（3）需要计算f（2）和f（1），可以看到f（2）被重复计算了。
递归是将一个问题划分为多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。
public int Fibonacci(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]; }
考虑到第i项只与第i-1项和第i-2项有关，因此只需要存储前两项的值就能求解第i项，从而将空间复杂度由O（N）降低为O（1）。
public int Fibonacci(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小鱼40，因此可以将前40 项的结果先行计算，之后就能O（1）时间复杂度得到第n项的值。
public class Solution { private int[] fib = new int[40]; public Solution() { 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]; } }
原文：https://www.cnblogs.com/ziytong/p/12096141.html