Memoization Top Down DP in DSA Java - Execution Trace

Concept Flow - Memoization Top Down DP

Start with problem input

↓

Check if result in memo?

Yes→Return memoized result

No↓

Compute result recursively

↓

Store result in memo

↓

Return result

↓

Combine results to solve original problem

The flow starts by checking if the answer is already saved. If yes, return it. If no, compute recursively, save it, then return.

Execution Sample

DSA Java

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

This code computes Fibonacci numbers using top-down memoization to avoid repeated calculations.

Execution Table

Step	Operation	n	Memo Before	Recursive Calls	Memo After	Returned Value
1	fib(4) called	4	[-1, -1, -1, -1, -1]	[fib(3), fib(2)]	[-1, -1, -1, -1, -1]	pending
2	fib(3) called	3	[-1, -1, -1, -1, -1]	[fib(2), fib(1)]	[-1, -1, -1, -1, -1]	pending
3	fib(2) called	2	[-1, -1, -1, -1, -1]	[fib(1), fib(0)]	[-1, -1, -1, -1, -1]	pending
4	fib(1) base case	1	[-1, -1, -1, -1, -1]	none	[-1, -1, -1, -1, -1]	1
5	fib(0) base case	0	[-1, -1, -1, -1, -1]	none	[-1, -1, -1, -1, -1]	0
6	fib(2) memoize	2	[-1, -1, -1, -1, -1]	none	[-1, -1, 1, -1, -1]	1
7	fib(1) base case	1	[-1, -1, 1, -1, -1]	none	[-1, -1, 1, -1, -1]	1
8	fib(3) memoize	3	[-1, -1, 1, -1, -1]	none	[-1, -1, 1, 2, -1]	2
9	fib(2) memo hit	2	[-1, -1, 1, 2, -1]	none	[-1, -1, 1, 2, -1]	1
10	fib(4) memoize	4	[-1, -1, 1, 2, -1]	none	[-1, -1, 1, 2, 3]	3
11	Return final result	4	[-1, -1, 1, 2, 3]	none	[-1, -1, 1, 2, 3]	3

💡 fib(4) returns 3 after memoizing all needed subproblems

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	Final
n	4	2	3	4	4
memo	[-1, -1, -1, -1, -1]	[-1, -1, 1, -1, -1]	[-1, -1, 1, 2, -1]	[-1, -1, 1, 2, 3]	[-1, -1, 1, 2, 3]
Returned Value	pending	1	2	3	3

Key Moments - 3 Insights

Why do we check memo[n] before computing fib(n)?

Because if memo[n] is not -1, it means fib(n) was already computed and saved, so we return it immediately to avoid repeated work. See steps 9 and 10 in execution_table.

What happens when n is 0 or 1?

These are base cases returning n directly without recursion. See steps 4 and 5 where fib(1) and fib(0) return 1 and 0 respectively.

How does memoization reduce the number of recursive calls?

Once a fib(n) is computed and stored in memo, future calls for fib(n) return instantly without recursion, as shown in step 9 where fib(2) returns from memo.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what value is stored in memo[2] after fib(2) finishes?

A 1

B 2

C -1

D 3

💡 Hint

Check the 'Memo After' column at step 6 in execution_table.

At which step does fib(3) get its value memoized?

A Step 9

B Step 7

C Step 8

D Step 10

💡 Hint

Look for the step where memo[3] changes from -1 to a number in execution_table.

If memo was not used, how would the number of recursive calls change?

A They would decrease

B They would increase significantly

C They would stay the same

D They would be zero

💡 Hint

Refer to key_moments about memoization reducing repeated calls.

Concept Snapshot

Memoization Top Down DP:
- Use recursion with a memo array to save results
- Check memo before computing to avoid repeats
- Base cases return directly
- Store computed results in memo
- Return memoized results to speed up
- Example: Fibonacci with memo[n] stores fib(n)

Full Transcript

Memoization in top-down dynamic programming means saving results of recursive calls in a memo array. When the function is called with a value n, it first checks if the answer is already in memo. If yes, it returns that saved answer immediately. If not, it computes the answer recursively, saves it in memo, then returns it. This avoids repeated calculations of the same subproblems. For example, in Fibonacci, fib(2) is computed once and saved. Later calls to fib(2) return instantly from memo. Base cases like fib(0) and fib(1) return directly without recursion. This technique speeds up recursion by trading space for time.

Practice

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

easy

A. To increase the size of the input for better accuracy

B. To sort the input data before processing

C. To store results of subproblems to avoid repeated calculations

D. To convert recursive code into iterative code

Solution

1. Step 1: Understand memoization role

   Memoization saves answers of smaller problems so they are not recalculated.

2. Step 2: Compare options

   Only To store results of subproblems to avoid repeated calculations correctly describes storing subproblem results to avoid repeats.

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 changes recursion to iteration
• Believing memoization increases input size

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

easy

A. int memo[] = new int();

B. int memo = new int[n];

C. int[] memo = new int[];

D. int[] memo = new int[n+1];

Solution

1. Step 1: Check Java array declaration syntax

   Correct syntax for array with size n+1 is: int[] memo = new int[n+1];

2. Step 2: Identify errors in other options

   int memo = new int[n]; declares int, not array; C misses size; D uses wrong constructor syntax.

3. Final Answer:

   int[] memo = new int[n+1]; -> Option D

4. Quick Check:

   Array declaration = int[] memo = new int[size] [OK]

Hint: Use int[] memo = new int[n+1] for memo arrays [OK]

Common Mistakes:

• Declaring memo as int instead of int[]
• Not specifying array size when creating
• Using parentheses instead of brackets for arrays

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

public class FibMemo {
  static int[] memo;
  public static 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];
  }
  public static void main(String[] args) {
    int n = 5;
    memo = new int[n+1];
    for (int i = 0; i <= n; i++) memo[i] = -1;
    System.out.println(fib(n));
  }
}

medium

A. 5

B. 8

C. 3

D. Error due to uninitialized memo

Solution

1. Step 1: Understand Fibonacci calculation with memo

   fib(5) = fib(4) + fib(3), recursively calculated and stored in memo.

2. Step 2: Calculate fib(5) step-by-step

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

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Forgetting to initialize memo with -1
• Assuming memo causes errors if not initialized

4. Identify the bug in this memoized Fibonacci code snippet:

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

public static void main(String[] args) {
  int n = 4;
  int[] memo = new int[n+1];
  System.out.println(fib(n, memo));
}

medium

A. Memo array not initialized with -1, causing wrong cache checks

B. Base case should return 0 for n <= 1

C. Memo array size is too small

D. fib function missing return statement

Solution

1. Step 1: Check memo initialization and cache check

   Memo array defaults to 0; fib(0)=0, so memo[n]!=0 check fails for fib(0).

2. Step 2: Explain why -1 initialization is needed

   Initialize memo with -1 to distinguish uncalculated from zero results.

3. Final Answer:

   Memo array not initialized with -1, causing wrong cache checks -> Option A

4. Quick Check:

   Initialize memo with -1 to avoid false cache hits [OK]

Hint: Initialize memo with -1 to mark unvisited states [OK]

Common Mistakes:

• Assuming 0 means unvisited in memo
• Changing base case incorrectly
• Using wrong memo array size

5. Given the top-down memoized code for the coin change problem below, what is the output for coins = {1, 2} and amount = 4?

public class CoinChange {
  static int[] memo;
  public static int countWays(int amount, int[] coins) {
    if (amount == 0) return 1;
    if (amount < 0) return 0;
    if (memo[amount] != -1) return memo[amount];
    int ways = 0;
    for (int coin : coins) {
      ways += countWays(amount - coin, coins);
    }
    memo[amount] = ways;
    return ways;
  }
  public static void main(String[] args) {
    int[] coins = {1, 2};
    int amount = 4;
    memo = new int[amount + 1];
    for (int i = 0; i <= amount; i++) memo[i] = -1;
    System.out.println(countWays(amount, coins));
  }
}

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Understand problem and recursion

   Count ways to make 4 using coins 1 and 2, summing ways for amount-coin recursively.

2. Step 2: Calculate ways for amount=4

   Ways(4) = Ways(3)+Ways(2); Ways(3)=Ways(2)+Ways(1); Ways(2)=Ways(1)+Ways(0); Ways(1)=Ways(0)+Ways(-1); base cases: Ways(0)=1, Ways(-1)=0.

3. Step 3: Calculate values bottom-up

   Ways(0)=1; Ways(1)=1+0=1; Ways(2)=1+1=2; Ways(3)=2+1=3; Ways(4)=3+2=5.

4. Step 4: Re-check sum

   Actually, the code counts permutations, so for amount=4 with coins {1,2}, total ways = 5.

5. Final Answer:

   5 -> Option B

6. Quick Check:

   Number of ways to make 4 with {1,2} = 5 [OK]

Hint: Count ways recursively, memoize to avoid repeats [OK]

Common Mistakes:

• Confusing combinations with permutations
• Not initializing memo with -1
• Miscounting base cases