带备忘录和dp的递归

#include <iostream>
#include <vector>

using namespace std;

int helper(vector<int> &m, int n);
int fib(int n);

int fib(int n)
{
    if(n < 1)
    {
        return 0;
    }
    vector<int> m(n + 1, 0);
    return helper(m, n);
}

int helper(vector<int>&m, int n)
{
    if(n == 1 || n == 2) 
    {
        return 1;
    }
    if (m[n] != 0)
    {
        return m[n];
    }
    m[n] = helper(m, n - 1) + helper(m, n - 2);
    return m[n];
} 

int main()
{
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int fib(int n);

int fib(int n)
{
    if(n < 1)
    {
        return 0;
    }
    vector<int> dp(n + 1, 0);
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++) 
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main()
{
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

#include <iostream>

using namespace std;

int fib(int n);

int fib(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    int a, b, sum;
    a = b = 1;
    for (int i = 3; i <= n; i++) 
    {
        sum = a + b;
        a = b;
        b = sum;
    }
    return sum;
}

int main()
{
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}