[jzof] 10 Fibonacci series

Use an array to store the calculated value , Prevent double counting ：

class Solution {
    
public:
    int f[50]{
    0};
    int Fibonacci(int n) {
    
        if (n <= 2) return 1;
        if (f[n] > 0) return f[n];
        return f[n] = (Fibonacci(n-1)+Fibonacci(n-2));
    }
};

Dynamic programming ：

class Solution {
    
public:
    int dp[50]{
    0};
    int Fibonacci(int n) {
    
        dp[1] = 1, dp[2] =1;
        for (int i = 3 ; i <= n ; i ++) dp[i] = dp[i-1]+dp[i-2];
        return dp[n];
    }
};

Continue to optimize dynamic programming method ( Reduce space complexity )：

class Solution {
    
public:
    int Fibonacci(int n) {
    
        int a = 1 , b = 1 , c = 1;
        for (int i = 3 ; i <= n ; i ++) {
    
            c = a+b , a = b , b = c;
        }
        return c;
    }
};