动态规划 fibonacci数列

在传统的fibonacci数列的基础上使用动态规划，即申请一个dp数组用来存储计算过的子阶乘，当重复遇到这个阶乘时可以直接返回。使计算的复杂度大大下降。这是由于fibonacci数列存在重复子问题以及最优子结构决定的。

/*
 * @lc app=leetcode id=509 lang=cpp
 *
 * [509] Fibonacci Number
 */
class Solution {
    int dp[120];
public:
    int fib(int N) {
        for(int i=0;i<120;i++)
        {
            dp[i] = -1;
        }

        return f(N);

        
    }
    int f(int n)
    {
         if(n==1)
              return 1;
         if(n==0)
              return 0;
     if(dp[n]!=-1)//说明已经计算过
       return dp[n];
     else
     {
       dp[n]=f(n-1)+f(n-2);
       return dp[n];
     }
    }
};