Memoization Top Down DP in DSA Go - 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 computed result

The flow shows checking memo before computing, computing recursively if needed, storing result, then returning it.

Execution Sample

DSA Go

func fib(n int, memo map[int]int) int {
  if n <= 1 {
    return n
  }
  if val, ok := memo[n]; ok {
    return val
  }
  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 work.

Execution Table

Step	Operation	n	Memo Before	Recursive Calls	Memo After	Returned Value
1	Call fib(4)	4	{}	fib(3), fib(2)	{4: ?}	?
2	Call fib(3)	3	{}	fib(2), fib(1)	{3: ?}	?
3	Call fib(2)	2	{}	fib(1), fib(0)	{2: ?}	?
4	Call fib(1)	1	{}	None	{}	1
5	Call fib(0)	0	{}	None	{}	0
6	Compute fib(2)	2	{}	None	{2:1}	1
7	Compute fib(3)	3	{2:1}	None	{2:1, 3:2}	2
8	Call fib(2)	2	{2:1, 3:2}	None	{2:1, 3:2}	1
9	Compute fib(4)	4	{2:1, 3:2}	None	{2:1, 3:2, 4:3}	3
10	Return final result	4	{2:1, 3:2, 4:3}	None	{2:1, 3:2, 4:3}	3

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

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 9	Final
n	4	1	2	3	4	4
memo	{}	{}	{2:1}	{2:1, 3:2}	{2:1, 3:2, 4:3}	{2:1, 3:2, 4:3}
Returned Value	N/A	1	1	2	3	3

Key Moments - 3 Insights

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

Checking memo first (see Step 2 and Step 8) avoids recomputing fib(n) if already solved, saving time.

What happens when n is 0 or 1?

For n=0 or 1 (Step 4 and 5), the function returns n directly without recursion, as base cases.

How does memoization prevent repeated recursive calls?

Once fib(k) is computed and stored in memo (Step 6 and 7), future calls for fib(k) return memoized value immediately (Step 8).

Visual Quiz - 3 Questions

Look at the execution table, what is the memo content after Step 7?

A {"2":1, "3":2}

B {"2":1}

C {}

D {"4":3}

💡 Hint

Check the 'Memo After' column at Step 7 in the execution table.

At which step does fib(1) return without further recursion?

A Step 6

B Step 8

C Step 4

D Step 9

💡 Hint

Look for fib(1) calls with no recursive calls in the 'Recursive Calls' column.

If memo already contained fib(2), how would Step 3 change?

A fib(2) would cause an error

B fib(2) would return immediately without recursive calls

C fib(2) would still call fib(1) and fib(0)

D fib(2) would compute fib(3) again

💡 Hint

Memoization avoids repeated recursion by returning stored results early.

Concept Snapshot

Memoization Top Down DP:
- Use recursion with a memo (cache) to store results
- Check memo before computing to avoid repeats
- Store computed results in memo
- Return memoized or computed value
- Speeds up exponential recursion to linear time

Full Transcript

Memoization in top-down dynamic programming means saving results of recursive calls in a memo dictionary. When the function is called with a value n, it first checks if the answer is already in the memo. If yes, it returns that answer immediately. If not, it computes the answer recursively, stores it in the memo, and returns it. This avoids repeated work and speeds up the program. For example, in Fibonacci, fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). Base cases fib(1) and fib(0) return immediately. Then results are stored and reused. This process is shown step-by-step in the execution table and variable tracker.

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 convert recursive code into iterative code

D. To store results of subproblems to avoid repeated calculations

Solution

1. Step 1: Understand memoization concept

   Memoization saves the results of subproblems so they are not recalculated multiple times.

2. Step 2: Compare options

   Only To store results of subproblems to avoid repeated calculations correctly describes this purpose; others describe unrelated actions.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store subproblem results [OK]

Hint: Memoization means caching 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 Go code snippets correctly initializes a memoization map for storing integer results?

easy

A. memo := []int{}

B. memo := map[string]string{}

C. memo := make(map[int]int)

D. memo := new(int)

Solution

1. Step 1: Identify correct map initialization

   In Go, a map from int to int is created with make(map[int]int).

2. Step 2: Check other options

   memo := []int{} is a slice, not a map; C uses wrong types; D creates a pointer to int, not a map.

3. Final Answer:

   memo := make(map[int]int) -> Option C

4. Quick Check:

   Map[int]int = make(map[int]int) [OK]

Hint: Use make(map[keyType]valueType) to create memo map [OK]

Common Mistakes:

• Using slice instead of map for memo
• Wrong key or value types in map
• Using new(int) which is a pointer, not a map

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

package main
import "fmt"

var memo = make(map[int]int)

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

func main() {
    fmt.Println(fib(5))
}

medium

A. 5

B. 8

C. 13

D. Error: stack overflow

Solution

1. Step 1: Trace fib(5) calls with memoization

   fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), etc. 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 A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Memoization avoids repeated fib calls, output fib(5)=5 [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memo and recalculating
• Expecting runtime error due to recursion

4. Identify the bug in this Go memoized Fibonacci function and select the fix:

func fib(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

func main() {
    fmt.Println(fib(5, nil))
}

medium

A. Remove memo parameter from fib

B. Initialize memo map before passing to fib

C. Change base case to n < 0

D. Return 0 when n <= 1

Solution

1. Step 1: Analyze memo usage in fib call

   fib is called with memo = nil, so accessing memo[n] causes runtime panic.

2. Step 2: Fix by initializing memo map before first call

   Pass a properly initialized map, e.g., make(map[int]int), to avoid nil map access.

3. Final Answer:

   Initialize memo map before passing to fib -> Option B

4. Quick Check:

   Nil map causes panic; initialize before use [OK]

Hint: Always initialize map before passing to recursive function [OK]

Common Mistakes:

• Passing nil map causing runtime panic
• Changing base case incorrectly
• Removing memo parameter loses memoization

5. Given the following Go code for memoized calculation of the number of ways to climb stairs (1 or 2 steps at a time), what is the output of countWays(4, memo)?

package main
import "fmt"

func countWays(n int, memo map[int]int) int {
    if n == 0 {
        return 1
    }
    if n < 0 {
        return 0
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = countWays(n-1, memo) + countWays(n-2, memo)
    return memo[n]
}

func main() {
    memo := make(map[int]int)
    fmt.Println(countWays(4, memo))
}

hard

A. 5

B. 7

C. 8

D. Error: infinite recursion

Solution

1. Step 1: Understand problem and base cases

   countWays(0) = 1 (one way to stand still), countWays(n<0) = 0 (no way). Ways to climb n steps = sum of ways for n-1 and 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 = fib(n+1), so countWays(4) = 5 [OK]

Common Mistakes:

• Confusing base cases causing wrong counts
• Forgetting to initialize memo map
• Expecting infinite recursion without memo