509. Fibonacci Number斐波那契数列

网址：https://leetcode.com/problems/fibonacci-number/

原始的斐波那契数列

运用自底向上的动态规划最佳！

可以定义vector数组，但是占用较多内存空间

 1 class Solution {
 2 public:
 3     int fib(int N) {
 4         int sum;
 5         if(N == 0)
 6             return 0;
 7         if(N == 1)
 8             return 1;
 9         vector<int> t(N+1,0);
10         t[0] = 0;
11         t[1] = 1;
12         for(int i=2;i<=N;i++)
13         {
14             t[i] = t[i-1] + t[i-2];
15         }
16         return t[N];
17     }
18 };

直接定义三个变量，不断更新它们的值

 1 class Solution {
 2 public:
 3     int fib(int N) {
 4         int a,b=1,c=0;
 5         if(N == 0)
 6             return 0;
 7         if(N == 1)
 8             return 1;
 9         for(int i=2;i<=N;i++)
10         {
11             a = b+c;
12             c = b;
13             b = a;
14         }
15         return a;
16     }
17 };