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.

Practice

1. What is the main purpose of memoization in top-down dynamic programming?

easy

A. To convert recursive code into iterative code

B. To sort the input data before processing

C. To store results of subproblems to avoid repeated calculations

D. To increase the number of recursive calls

Solution

1. Step 1: Understand memoization concept

   Memoization saves answers of smaller problems so they don't get solved again.

2. Step 2: Identify its role in top-down DP

   It stores subproblem results during recursion to speed up the process.

3. Final Answer:

   To store results of subproblems to avoid repeated calculations -> Option C

4. Quick Check:

   Memoization = Store subproblem results [OK]

Hint: Memoization means saving answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting
• Thinking memoization converts recursion to iteration
• Believing memoization increases recursive calls

2. Which of the following is the correct way to declare a memoization array for Fibonacci numbers in C?

easy

A. int memo[] = new int[100];

B. int memo[100] = {0};

C. int memo = new int[100];

D. int memo(100);

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with fixed size and optional initialization like int memo[100] = {0};

2. Step 2: Check each option

   int memo[100] = {0}; uses correct C syntax. Options A and C use Java/C++ style. int memo(100); is invalid in C.

3. Final Answer:

   int memo[100] = {0}; -> Option B

4. Quick Check:

   C array declaration = int memo[100] = {0}; [OK]

Hint: C arrays use fixed size with square brackets [OK]

Common Mistakes:

• Using Java or C++ style array declarations in C
• Forgetting to initialize memo array to zero
• Using parentheses instead of brackets for arrays

3. What will be the output of the following C code snippet using memoization for Fibonacci?

int memo[10] = {0};
int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

int main() {
  printf("%d", fib(5));
  return 0;
}

medium

A. 0

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace fib(5) calls and memo usage

   fib(5) calls fib(4) + fib(3), and so on. Memo stores results to avoid repeats.

2. Step 2: Calculate fib(5)

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Assuming memo array starts with all ones

4. Identify the error in this memoized Fibonacci function in C:

int memo[10];
int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

int main() {
  printf("%d", fib(5));
  return 0;
}

medium

A. memo array is not initialized to -1

B. fib function should return void

C. Base case should be n == 0 only

D. memo array size is too small

Solution

1. Step 1: Check memo array initialization

   Memo is checked for -1 but never initialized, so contains garbage values.

2. Step 2: Understand impact on memoization

   Without initialization, memo[n] != -1 may be true incorrectly, causing wrong returns.

3. Final Answer:

   memo array is not initialized to -1 -> Option A

4. Quick Check:

   Initialize memo to -1 before use [OK]

Hint: Always initialize memo array before use [OK]

Common Mistakes:

• Forgetting to initialize memo array
• Changing base case incorrectly
• Assuming default zero initialization in C

5. Given the following top-down memoized code to count ways to climb stairs (1 or 2 steps), what is the output of countWays(4)? Assume memo array is initialized with -1.

int memo[100];
int countWays(int n) {
  if (n == 0) return 1;
  if (n < 0) return 0;
  if (memo[n] != -1) return memo[n];
  memo[n] = countWays(n-1) + countWays(n-2);
  return memo[n];
}

int main() {
  for(int i=0; i<100; i++) memo[i] = -1;
  printf("%d", countWays(4));
  return 0;
}

hard

A. 5

B. 7

C. 8

D. 4

Solution

1. Step 1: Understand problem and base cases

   Ways to climb 0 steps = 1, negative steps = 0, ways(n) = ways(n-1)+ways(n-2).

2. Step 2: Calculate countWays(4)

   countWays(1)=1, countWays(2)=2, countWays(3)=3, countWays(4)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Ways to climb 4 steps = 5 [OK]

Hint: Count ways follow Fibonacci pattern starting with 1,1 [OK]

Common Mistakes:

• Confusing base cases for counting ways
• Not initializing memo array
• Mixing up countWays with Fibonacci values