剑指offer系列4：斐波那契数列

剑指offer第九题，这个题很古老了。第一个想到的肯定是递归，很简单。

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     int Fibonacci(int n) {
 7         if (n == 0)
 8         {
 9             return 0;
10         }
11         if (n==1||n==2)
12         {
13             return 1;
14         }
15         else
16         {
17             return Fibonacci(n-1)+ Fibonacci(n-2);
18         }
19 
20     }
21 };
22 int main()
23 {
24     Solution so;
25     int re = so.Fibonacci(5);
26     cout << re<<endl;
27     return 0;
28 }

第二种是我在github上看到的思路，变递归为for循环

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         if (n == 0)
 5         {
 6             return 0;
 7         }
 8         if (n==1||n==2)
 9         {
10             return 1;
11         }
12         else
13         {
14             int one = 1,two=1,cur=0;
15             for (int i = 3; i <= n; i++)
16             {
17                 cur = one + two;
18                 one = two;
19                 two = cur;
20             }
21             return cur;
22         }
23 
24     }
25 };

思路是用两个变量存要加的两项的值，用for循环一直更新，递归的复杂度是指数，for循环的复杂度是0（n）。

与这个题类似的还有青蛙跳台阶和用小矩形覆盖大矩形的问题，都可以归类为斐波那契数列。在遇到这种问题时，如何将问题转换为合适的数学模型很重要。

----------------------------------------

更新一个变态跳台阶，先分析变态跳台阶的数学特征，得出的结论是f（n）=f(n-1)+f(n-2)+........+f(1)+1;

有了这个结论写代码就很容易了

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     int jumpFloorII(int n) {
 7             if (n == 0)
 8             {
 9                 return 0;
10             }
11             if (n == 1 )
12             {
13                 return 1;
14             }
15             else
16             {
17                 int  re = 0;
18                 for (int i=1; i <n; i++)
19                 {
20                     re = re + jumpFloorII(i);
21                 }
22                 return re+1;
23             }
24 
25     }
26 };
27 int main()
28 {
29     Solution so;
30     int re = so.jumpFloorII(6);
31     cout << re<<endl;
32     return 0;
33 }

我看了github上的答案，还可以将问题的表达式整理成f（n）=2xf（n-1），确实简洁了很多，不过原理上差不多，都要调用n-1次函数才能得到结果。这个题是我不参考答案自己做出来的第一个，好开心(*^▽^*)！