Memoization Top Down DP in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of dynamic programming?

Memoization is a technique where we store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

beginner

How does top-down dynamic programming differ from bottom-up dynamic programming?

Top-down DP solves the problem by breaking it down recursively and storing results (memoization), while bottom-up DP solves smaller subproblems first and builds up to the solution iteratively.

beginner

In C, what data structure is commonly used to store memoized results for top-down DP?

An array or a 2D array is commonly used to store memoized results, where each index corresponds to a subproblem's input parameters.

intermediate

Why is memoization important in recursive solutions for problems like Fibonacci numbers?

Without memoization, recursive solutions recompute the same subproblems many times, causing exponential time. Memoization reduces this to linear time by storing and reusing results.

intermediate

What is a key step to implement memoization in a top-down DP function in C?

Initialize a memo array with a special value (like -1) to indicate uncomputed states, then check this array before computing a subproblem to reuse stored results.

What does memoization help avoid in recursive DP solutions?

A Using extra memory

B Repeated calculations of the same subproblems

C Writing recursive functions

D Using loops

Memoization stores results of subproblems to avoid recalculating them multiple times.

In top-down DP, when do we store the result of a subproblem?

A Before solving the subproblem

B We never store results

C Only for the final answer

D After solving the subproblem

We store the result after computing a subproblem to reuse it later.

Which of these is a common initial value to mark uncomputed states in memo arrays?

A 0

B 1

C -1

D 100

Using -1 helps identify which states have not been computed yet.

What is the time complexity improvement when using memoization for Fibonacci numbers?

A From O(2^n) to O(n)

B No improvement

C From O(n) to O(1)

D From O(n^2) to O(n)

Memoization reduces exponential time O(2^n) to linear time O(n) for Fibonacci.

Which programming construct is essential for top-down DP?

A Recursion

B Iteration with for loops

C Switch statements

D Goto statements

Top-down DP uses recursion to break down problems.

Explain how memoization works in a top-down dynamic programming approach.

Think about how you remember answers to avoid solving the same problem twice.

Describe the steps to implement memoization for a recursive Fibonacci function in C.

Focus on how you use an array to save and reuse results.

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