Memoization Top Down DP in DSA C

Mental Model

Remember answers to small problems so you don't solve them again.

Analogy: Like writing down answers to tricky homework questions so you can check them later instead of redoing the whole problem.

Problem -> Break into smaller problems -> Solve smaller problems -> Store answers in a table (memo) -> Use stored answers to build bigger answers

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using memoization

Goal: Find the 5th Fibonacci number efficiently by saving results of smaller Fibonacci calls

Step 1: Call fib(5), check memo, not found, so compute fib(4) and fib(3)

memo: [null, null, null, null, null, null]
fib calls stack: fib(5) -> fib(4), fib(3)

Why: We start with the big problem and break it down

Step 2: Call fib(4), check memo, not found, compute fib(3) and fib(2)

memo: [null, null, null, null, null, null]
fib calls stack: fib(5) -> fib(4) -> fib(3), fib(2)

Why: Keep breaking down until base cases

Step 3: Call fib(3), check memo, not found, compute fib(2) and fib(1)

memo: [null, null, null, null, null, null]
fib calls stack: fib(5) -> fib(4) -> fib(3) -> fib(2), fib(1)

Why: Breaking down further

Step 4: Call fib(2), check memo, not found, compute fib(1) and fib(0)

memo: [null, null, null, null, null, null]
fib calls stack: fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1), fib(0)

Why: Reach base cases

Step 5: fib(1) and fib(0) are base cases, return 1 and 0

memo: [null, null, null, null, null, null]

Why: Base cases have known answers

Step 6: Calculate fib(2) = fib(1) + fib(0) = 1 + 0 = 1, store in memo

memo: [null, null, 1, null, null, null]

Why: Save answer to avoid recomputation

Step 7: fib(1) is base case, return 1

memo unchanged

Why: Use known answer

Step 8: Calculate fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store in memo

memo: [null, null, 1, 2, null, null]

Why: Save answer for fib(3)

Step 9: Call fib(2), found in memo as 1, return 1

memo unchanged

Why: Reuse saved answer

Step 10: Calculate fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store in memo

memo: [null, null, 1, 2, 3, null]

Why: Save answer for fib(4)

Step 11: Call fib(3), found in memo as 2, return 2

memo unchanged

Why: Reuse saved answer

Step 12: Calculate fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store in memo

memo: [null, null, 1, 2, 3, 5]

Why: Save answer for fib(5)

Result:

memo: [null, null, 1, 2, 3, 5]
Answer: 5

Annotated Code

DSA C

#include <stdio.h>

#define MAX 100

int memo[MAX];

int fib(int n) {
    if (n <= 1) {
        return n; // base case
    }
    if (memo[n] != -1) {
        return memo[n]; // return saved answer
    }
    memo[n] = fib(n - 1) + fib(n - 2); // compute and save
    return memo[n];
}

int main() {
    int n = 5;
    for (int i = 0; i <= n; i++) {
        memo[i] = -1; // initialize memo
    }
    int result = fib(n);
    printf("%d\n", result);
    return 0;
}

if (n <= 1) { return n; }

return base case answer immediately

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

return saved answer if already computed

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

compute answer recursively and save it

Output

5

Complexity Analysis

Time: O(n) because each number from 0 to n is computed once and saved

Space: O(n) for the memo array storing results for each subproblem

vs Alternative: Without memoization, time is O(2^n) due to repeated calculations; memoization reduces it to O(n)

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA C

if (n <= 1) { return n; }

n = 1 (smallest non-zero input)

Returns 1 immediately as base case

DSA C

if (n <= 1) { return n; }

Repeated calls for same n

Returns saved answer from memo without recomputation

DSA C

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

When to Use This Pattern

When a problem asks for a value defined by smaller subproblems and has overlapping calls, use memoization top down DP to save repeated work.

Common Mistakes

Mistake: Not initializing memo array to -1, causing wrong reuse of uninitialized values
Fix: Initialize memo array elements to -1 before starting recursion

Mistake: Not checking memo before recursive calls, leading to repeated work
Fix: Always check memo before computing subproblems

Summary

It saves answers to smaller problems to avoid repeating work in recursion.

Use it when a problem has overlapping subproblems and recursion.

The key is to store and reuse answers instead of recomputing.