斐波那契数列问题的两种解决方法

1次阅读

共计 1210 个字符，预计需要花费 4 分钟才能阅读完成。

【本文版权归微信公众号 ” 代码艺术 ”（ID：onblog）所有，若是转载请务必保留本段原创声明，违者必究。若是文章有不足之处，欢迎关注微信公众号私信与我进行交流！】

斐波那契数列 指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..

这个数列从第 3 项开始，每一项都等于前两项之和。

简单来说，斐波那契数列 可以用下面这个公式来表示。

{ 0   ,n=0
{ 1   ,n=1
{f(n-1)+f(n-2) ,n>1

关于斐波那契数列衍生的算法题层出不穷，比如青蛙跳台阶问题等（题目：一只青蛙一次可以跳 1 级台阶，也可以条 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。），斐波那契数列问题的解法主要有两种，下面来看一下。

long fibonacci(int n){if (n==0){return 0;}
     if (n==1){return 1;}
     return fibonacci(n-1)+fibonacci(n-2);
 }

上面的代码已经非常直观和简单的展示了递归的思想。但这种解决问题的方式却是最差的。比如我们在求解 f(10)时，需要先求 f(9)和 f(8)。同样，在求 f(9)时，需要先求 f(8)和 f(7)….. 这种递归方法会导致重复计算的节点数随着 n 的增大而急剧增大，它的时间复杂度是以 n 的指数的方式递增的。

long fibonaccis(int n){if (n==0){return 0;}
     if (n==1){return 1;}
     int zero = 0;//f(0)
     int one = 1; //f(1)
     int two = 0;
     for (int i = 2; i <= n; i++) {two = one+zero; //f(n)=f(n-1)+f(n-2)
         zero = one;
         one = two;
     }
     return two;
 }

在上面的代码中，我们把已经得到的数列中间项保存起来，在下次需要计算的时候我们先查找一下，如果前面已经计算过就不用再重复计算了。

这个算法的流程是：

f(2)=f(1)+f(0)
f(3)=f(2)+f(1)
f(4)=f(3)+f(2)
…