剑指offer——08斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

有多种方法，简单的循环、递归、动态规划；

 1 class Solution01 {
 2 public:
 3     int Fibonacci(int n) {
 4         int a = 0, b = 1, c;
 5         for (int i = 2; i <= n; ++i)
 6         {
 7             c = a + b;
 8             a = b;
 9             b = c;
10         }
11         return n == 0 ? 0 : b;
12     }
13 };
14
15 class Solution02 {
16 public:
17     int Fibonacci(int n) {
18         if (n <= 1)
19             return n;
20         return Fibonacci(n - 1) + Fibonacci(n - 2);
21     }
22 };
23
24 class Solution03 {
25 public:
26     int Fibonacci(int n) {
27         if (n <= 1)
28             return n;
29         vector<int>dp(n + 1);
30         dp[0] = 0, dp[1] = 1;
31         for (int i = 2; i <= n; ++i)
32             dp[i] = dp[i - 1] + dp[i - 2];
33         return dp[n];
34     }
35 };