Memoization Top Down DP in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following Go code that uses memoization to compute Fibonacci numbers?

DSA Go

package main
import "fmt"
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() {
    memo := make(map[int]int)
    fmt.Println(fib(6, memo))
}

A 8

B 21

C 13

D 5

💡 Hint

Remember Fibonacci sequence starts 0,1,1,2,3,5,8,13...

The Fibonacci sequence is 0,1,1,2,3,5,8,13,... so fib(6) = 8.

🧠 Conceptual

intermediate

Memoization Purpose in Top Down DP

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

A To store intermediate results to avoid repeated calculations

B To sort the input data before processing

C To convert recursive code into iterative code

D To reduce memory usage by deleting variables

💡 Hint

Think about how recursion can repeat work.

Memoization saves results of expensive function calls and returns the cached result when the same inputs occur again, avoiding repeated work.

🔧 Debug

advanced

Identify the Error in Memoized Fibonacci

What error will this Go code produce when run?

DSA Go

package main
import "fmt"
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() {
    var memo map[int]int
    fmt.Println(fib(5, memo))
}

A 5

B 0

C panic: assignment to entry in nil map

D compile error: undefined variable memo

💡 Hint

Check how the map memo is initialized.

The map memo is declared but not initialized, so it is nil. Writing to a nil map causes a runtime panic.

🚀 Application

advanced

Memoization in Climbing Stairs Problem

Given the climbing stairs problem where you can climb 1 or 2 steps, what is the output of this memoized Go function for input 4?

DSA Go

package main
import "fmt"
func climbStairs(n int, memo map[int]int) int {
    if n <= 2 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo)
    return memo[n]
}
func main() {
    memo := make(map[int]int)
    fmt.Println(climbStairs(4, memo))
}

A 6

B 5

C 4

D 7

💡 Hint

Number of ways to climb 4 steps with 1 or 2 steps at a time.

Ways to climb 4 steps: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 = 5 ways.

❓ Predict Output

expert

Output of Memoized Coin Change Ways

What is the output of this Go code that uses memoization to count ways to make change for amount 5 with coins [1,2,5]?

DSA Go

package main
import "fmt"
func coinChange(coins []int, amount int, index int, memo map[string]int) int {
    key := fmt.Sprintf("%d-%d", amount, index)
    if val, ok := memo[key]; ok {
        return val
    }
    if amount == 0 {
        return 1
    }
    if amount < 0 || index == len(coins) {
        return 0
    }
    include := coinChange(coins, amount-coins[index], index, memo)
    exclude := coinChange(coins, amount, index+1, memo)
    memo[key] = include + exclude
    return memo[key]
}
func main() {
    coins := []int{1, 2, 5}
    memo := make(map[string]int)
    fmt.Println(coinChange(coins, 5, 0, memo))
}

A 3

B 5

C 2

D 4

💡 Hint

Count all combinations of coins that sum to 5.

The ways to make 5 are: 1+1+1+1+1, 1+1+1+2, 1+2+2, 5. Total 4 ways.

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