Memoization Top Down DP in DSA Java

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.

Start: 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 remembering results of smaller Fibonacci numbers

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

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

Why: We need fib(5), but no stored answer yet

Step 2: Call fib(4), check memo: empty, so compute fib(3) and fib(2)

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

Why: fib(4) depends on fib(3) and fib(2)

Step 3: Call fib(3), check memo: empty, so compute fib(2) and fib(1)

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

Why: fib(3) depends on fib(2) and fib(1)

Step 4: Call fib(2), check memo: empty, so compute fib(1) and fib(0)

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

Why: fib(2) depends on fib(1) and fib(0)

Step 5: fib(1) and fib(0) are base cases, return 1 and 0 respectively, store in memo

memo: [0, 1, 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: [0, 1, 1, null, null, null]

Why: Store result to avoid recomputation

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

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

Why: Use stored fib(2) and fib(1) to get fib(3)

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

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

Why: Use stored fib(3) and fib(2) to get fib(4)

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

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

Why: Use stored fib(4) and fib(3) to get fib(5)

Result:

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

Annotated Code

DSA Java

public class MemoizationTopDownDP {
    private static int fib(int n, int[] memo) {
        if (n <= 1) return n; // base case: fib(0)=0, fib(1)=1
        if (memo[n] != -1) return memo[n]; // return stored answer if available
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // store computed answer
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 5;
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) memo[i] = -1; // initialize memo with -1 meaning empty
        int result = fib(n, memo);
        System.out.println("memo: " + java.util.Arrays.toString(memo));
        System.out.println("Answer: " + result);
    }
}

if (n <= 1) return n; // base case: fib(0)=0, fib(1)=1

Return known base Fibonacci values

if (memo[n] != -1) return memo[n]; // return stored answer if available

Use memoized result to avoid recomputation

memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // store computed answer

Compute and save result for current n

Output

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

Answer: 5

Complexity Analysis

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

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

vs Alternative: Compared to naive recursion with O(2^n) time, memoization reduces repeated work to O(n)

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA Java

if (n <= 1) return n; // base case: fib(0)=0, fib(1)=1

n = 1 (small input)

Returns 1 immediately as base case

DSA Java

if (n <= 1) return n; // base case: fib(0)=0, fib(1)=1

Repeated calls with same n

Returns stored result from memo without recomputation

DSA Java

if (memo[n] != -1) return memo[n]; // return stored answer if available

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 with a sentinel value to detect computed results
Fix: Initialize memo array with -1 or another invalid value to mark uncomputed entries

Mistake: Forgetting to store the computed result in memo before returning
Fix: Assign the computed value to memo[n] before returning

Mistake: Not handling base cases correctly causing infinite recursion
Fix: Add base case checks for smallest inputs like n=0 and n=1

Summary

Stores answers to subproblems to avoid repeated calculations in recursive solutions.

Use when a problem can be broken into overlapping smaller problems solved recursively.

The key is to remember results so each subproblem is solved only once.

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