Memoization Top Down DP in DSA Go

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 -> Check if answer known -> If yes, use it -> If no, solve and save -> Combine answers

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using memoization

Goal: Find fib(5) efficiently by saving results of smaller fib calls

Step 1: Call fib(5), not in memory, so compute fib(4) and fib(3)

memo = {}
Computing fib(5)

Why: We need fib(5), but it depends on smaller fib numbers

Step 2: Call fib(4), not in memory, compute fib(3) and fib(2)

memo = {}
Computing fib(4)

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

Step 3: Call fib(3), not in memory, compute fib(2) and fib(1)

memo = {}
Computing fib(3)

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

Step 4: Call fib(2), not in memory, compute fib(1) and fib(0)

memo = {}
Computing fib(2)

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

Step 5: fib(1) and fib(0) are base cases, return 1 and 0

memo = {}
fib(1)=1, fib(0)=0

Why: Base cases stop recursion

Step 6: Calculate fib(2) = fib(1)+fib(0) = 1+0=1, save in memo

memo = {2:1}

Why: Save result to avoid recomputing fib(2)

Step 7: fib(1) is base case, return 1

memo = {2:1}

Why: Base case

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

memo = {2:1, 3:2}

Why: Save fib(3) result

Step 9: fib(2) found in memo, return 1 directly

memo = {2:1, 3:2}

Why: Use saved result to save time

Step 10: Calculate fib(4) = fib(3)+fib(2) = 2+1=3, save in memo

memo = {2:1, 3:2, 4:3}

Why: Save fib(4) result

Step 11: fib(3) found in memo, return 2 directly

memo = {2:1, 3:2, 4:3}

Why: Use saved result

Step 12: Calculate fib(5) = fib(4)+fib(3) = 3+2=5, save in memo

memo = {2:1, 3:2, 4:3, 5:5}

Why: Final answer saved

Result:

memo = {2:1, 3:2, 4:3, 5:5}
Answer: 5

Annotated Code

DSA Go

package main

import "fmt"

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

func main() {
    n := 5
    memo := make(map[int]int)
    result := fib(n, memo)
    fmt.Printf("fib(%d) = %d\n", n, result)
}

if n <= 1 { return n }

Return base case values 0 or 1 to stop recursion

if val, found := memo[n]; found { return val }

Return saved answer if already computed

memo[n] = fib(n-1, memo) + fib(n-2, memo)

Compute fib(n) by summing smaller fib calls and save result

Output

fib(5) = 5

Complexity Analysis

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

Space: O(n) for the memo map storing results and recursion call stack

vs Alternative: Naive recursion is O(2^n) due to repeated calls; memoization reduces it to O(n)

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Go

if n <= 1 { return n }

n = 1

Returns 1 immediately as base case

DSA Go

if n <= 1 { return n }

Repeated calls with same n

Uses memoized result, no recomputation

DSA Go

if val, found := memo[n]; found { return val }

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 checking memo before recursive calls, causing repeated work
Fix: Always check if result is in memo before computing

Mistake: Not saving computed results in memo after calculation
Fix: Store the computed value in memo before returning

Summary

Memoization saves answers to subproblems to avoid repeated work in recursion.

Use it when a problem has overlapping subproblems and recursive structure.

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 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