要求使用递归和非递归两种方法
public class Solution { public int Fibonacci(int n) { if(n<=0) return 0; if(n==1) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } }
上述递归代码之所以慢，是因为重复的计算太多了。
分析：其实我们可以发现每次就用到了最近的两个数，所以我们可以只存储最近的两个数
public class Solution { public int Fibonacci(int n) { if(n<=0) return 0; if(n==1) return 1; int sum = 0; int one = 1; int two = 0; for(int i = 2; i <= n; i++){ sum = one + two; two = one; one = sum; } return sum; } }
还能继续优化至复杂度为O(logn)，参考：
https://mp.weixin.qq.com/s/I2gtLVHwvXVY3S4AEV8UPA
https://mp.weixin.qq.com/s/hBVAuAq8mrqNWhO12NsgIQ
原文：https://www.cnblogs.com/HuangYJ/p/12836918.html