509 LeetCode 斐波那契数

题目描述：

思路：方法一：递归法：函数调用
方法二：动态规划：使用额外空间，用空间换时间
代码如下：

class Solution {
public:
    int fib(int N) {
    if(N==0)  return 0;
    if(N==1)  return 1; 
    return fib(N-1)+fib(N-2);
    }
};

class Solution {
public:
    int fib(int N) {
    if(N==0)  return 0;
    if(N==1)  return 1; 
    vector <int> res;
    res.push_back(0);
    res.push_back(1);
    for(int i=2;i<=N;i++){
        res.push_back(res[i-1]+res[i-2]);
    }
    return res[N];
    }
};