How to optimize Fibonacci using memoization in C++?

Question

I'm struggling with getting the correct implementation of finding the nth number in the Fibonacci sequence. More accurately, how to optimize it with DP.

I was able to correctly write it in the bottom-up approach:

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

But the top-down (memoized) approach is harder for me to grasp. This is what I put originally:

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

    // Lambda Function
    auto recurse = [&](int n) {
        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] = fib(n - 2) + fib(n - 1);
        return dp[n];
    };

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

...This was my first time using a C++ lambda function, though, so I also tried:

int recurse(int n, std::vector<int>& dp) {
    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] = fib(n - 2) + fib(n - 1);
    return dp[n];
}

int fib(int n) {
    std::vector<int> dp(n + 1, -1);
    recurse(n, dp);
    return dp.back();
}

...just to make sure. Both of these gave time limit exceeded errors on leetcode. This, obviously, seemed off, since DP/Memoization are optimization techniques. Is my top-down approach wrong? How do I fix it?

Answer 1

You set up the memoization storage in fib, and then create the recursive part of your solution in the lambda recurse. That means that here: dp[n] = fib(n - 2) + fib(n - 1); you really should call recurse not fib. But in order to do that with a lambda, you need to give the lambda to the lambda so to speak.

Example:

#include <iostream>
#include <vector>

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

    // Lambda Function
    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()
{
    std::cout << fib(12) << '\n';
}