Submission

PPPPP-----

Score: 50

User: pxsit

Problemset: อนุกรม

Language: cpp

Time: 0.002 second

Submitted On: 2024-12-14 21:11:44

#include <iostream>
#include <vector>

int fib(int n)
{
    std::vector<int> dp(n + 1, -1);

    
    auto recurse = [&dp](int n, auto &rec)
    {
        if (dp[n] != -1)
            return dp[n];

        if (n == 0)
        {
            dp[n] = 0;
            return 0;
        }
        if (n == 1)
        {
            dp[n] = 1;
            return 1;
        }

        dp[n] = rec(n - 2, rec) + rec(n - 1, rec);
        return dp[n];
    };

    recurse(n, recurse);
    return dp.back();
}

int main()
{
    int n;
    std::cin >> n;
    std::cout << fib(n) << '\n';
}