脚本宝典收集整理的这篇文章主要介绍了斐波那契数列(递归)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

来源：LeetCode

 

看到递归体都给了，直接放上去跑

public int fib(int n) {    if (n == 0) return 0;    if (n == 1) return 1;    return fib(n-1) + fib(n - 2)%1000000007;}结果超出时间限制，@R_45_1304@为2的n次方。由于每一次计算都是重复的，那么我们只需要避免重复的计算，使空间复杂度为O(N)

优化后

public int fib(int n) {    int[] MEMO = new int[n+1];    Arrays.fill(MEMO, -1);    return Recursion(n, MEMO)%1000000007;}public int Recursion(int num, int[] MEMO) {    //递归出口    if (num <= 1) {        return num;    }    //未计算过的    if (MEMO[num] == -1) {        MEMO[num] = Recursion(num - 1, MEMO) + Recursion(num - 2, MEMO);    }    //计算过的    return MEMO[num]%1000000007;}public static void main(String[] args) {    Fibonacci2 fibonacci2 = new Fibonacci2();    System.out.PRintln(fibonacci2.fib(10));}

脚本宝典总结

以上是脚本宝典为你收集整理的斐波那契数列(递归)全部内容，希望文章能够帮你解决斐波那契数列(递归)所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。