Dynamic Programming — A Deep Dive into Memoization with C

Introduction:

When working in an environment where memory and time matter, the logic behind the solution matters a lot. Solving problems efficiently is more important than just solving them. Many recursive solutions work but are too slow to be useful on large inputs. This is where Dynamic Programming (DP) shines.

In this blog post, we’ll explore one of the two core approaches of Dynamic Programming — Memoization — using the Fibonacci sequence as our guiding example. We’ll break down what it is, why it matters, and how to implement it in pure C with performance monitoring.

Whether you’re a beginner trying to understand recursion or an intermediate C programmer aiming to master algorithms, this is the blog for you.

What is Dynamic Programming?

Dynamic Programming is a technique for solving problems that can be broken down into overlapping subproblems with optimal substructure.

There are two primary approaches:

• Memoization (Top-Down): Store results of recursive calls to avoid recomputation.
• Tabulation (Bottom-Up): Build the solution iteratively.

This blog will focus on memoization, the more intuitive approach when you’re already using recursion.

The Fibonacci Problem:

Let’s begin with a classic example — the Fibonacci sequence:

F(0) = 0  
F(1) = 1  
F(n) = F(n-1) + F(n-2)

The solution for it in c is usually

int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

now this code is pretty solid but the issue is the repetition of with more and more numbers repetition grows exponentially

Visualization of Recursive Calls:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   ├── fib(1)
│   ├── fib(2)
├── fib(3)

As you can see, fib(2) and fib(3) are recalculated multiple times, and this process will occur more frequently as the number increases.

The time complexity of this approach is O(n^2) — exponential — which becomes impractical even at n = 40.

Now we'll try to reduce the time by using caching. The concept is simple: save repetitive calculations and access their results directly instead of recalculating them each time

Memoization: Optimizing with Caching

Memoization is a technique where we store the results of already computed subproblems in a table or array, and reuse them when needed instead of recomputing.

Get B.R.O.L.Y’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In C, we use a global or static array for this purpose.

✅ Memoized Fibonacci in C

#include <stdio.h>
#define MAX 100

int memo[MAX];

void init_memo() {
    for (int i = 0; i < MAX; i++)
        memo[i] = -1;
}

int fib(int n) {
    if (memo[n] != -1)
        return memo[n];

    if (n <= 1)
        memo[n] = n;
    else
        memo[n] = fib(n - 1) + fib(n - 2);

    return memo[n];
}

int main() {
    int n = 40;
    init_memo();
    printf("Fibonacci of %d = %d\n", n, fib(n));
    return 0;
}

Naive vs Memoized Performance:

We are going to test this, we’ll monitor the time taken to run each process based on the two different methods
The first one uses the normal algorithm

#include <stdio.h>
#include <time.h>


int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

int main()
{
    clock_t start = clock();
    long long result = fib(40);
    clock_t end = clock();

    double duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("Result: %ld\n", result);
    printf("Execution Time: %f seconds\n", duration);
    return (0);
}

This one amounted to

Result: 102334155
Execution Time: 1.977505 seconds

And the second method is when we’ll introduce memorizing and monitor the process time

#include <stdio.h>
#include <time.h>
#define MAX 200
int memo[MAX];

void init_memo() {
    for (int i = 0; i < MAX; i++)
        memo[i] = -1;
}

int fib(int n) {
    if (memo[n] != -1)
        return memo[n];

    if (n <= 1)
        memo[n] = n;
    else
        memo[n] = fib(n - 1) + fib(n - 2);

    return memo[n];
}

int main() {
    clock_t start = clock();
    long result = fib(40);
    clock_t end = clock();

    double duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("Result: %ld\n", result);
    printf("Execution Time: %f seconds\n", duration);
    return (0);
}

This one amounts to

Result: 102334155
Execution Time: 0.000006 seconds

Same answer in a record time, which shows how much we improved on it, but not to be all fascinated, one uses way more memory than the other because it has to cache all the old values

• 🟥 Naive Recursion: ~1.98 seconds
• 🟩 Memoization: ~0.000006 seconds

✅ Memoization results in a ~99.9997% performance improvement — solving the same problem almost instantly by caching previously computed values.

Memoization reduces the time complexity from O(2^n) to O(n)

When to use:

Use it when you have a recursive function that is called with the same argument repeatedly, and when the subproblems are overlapping

Conclusion

Memoization is a simple yet powerful optimization technique that transforms slow recursive algorithms into fast dynamic programming solutions. In this post, we took the classic Fibonacci problem, implemented it in C, and optimized it with memoization, reducing execution time dramatically.

By understanding and applying memoization, you’re taking a big step toward mastering Dynamic Programming and writing efficient C programs.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

This is it for now. Have a good day, and don’t forget to follow me on Medium and GitHub.