Memoization Top Down DP in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the memo map for storing computed results.

DSA Go

var memo = make(map[int]int[1])

Drag options to blanks, or click blank then click option'

A{}

B[]

C()

D<>

Attempts:

3 left

💡 Hint

Common Mistakes

Using square brackets or parentheses instead of curly braces.

Not initializing the map at all.

The memo map must be initialized with curly braces {} to create an empty map in Go.

2fill in blank

medium

Complete the code to check if the result for n is already computed in memo.

DSA Go

if val, ok := memo[[1]]; ok {
    return val
}

Drag options to blanks, or click blank then click option'

Aresult

Bval

Cmemo

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using the value variable instead of the key.

Using the map name instead of the key.

We check if the key n exists in the memo map to reuse the stored result.

3fill in blank

hard

Fix the error in the recursive call to compute Fibonacci with memoization.

DSA Go

result := fib([1] - 1) + fib([1] - 2)

Drag options to blanks, or click blank then click option'

Amemo

Bresult

Cn

Dval

Attempts:

3 left

💡 Hint

Common Mistakes

Using the result variable instead of the input parameter.

Using the memo map as argument.

The recursive calls must use the input parameter n to compute smaller subproblems.

4fill in blank

hard

Fill both blanks to store the computed result in memo and return it.

DSA Go

memo[[1]] = [2]
return memo[[1]]

Drag options to blanks, or click blank then click option'

An

Bresult

Cval

Dfib

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable names for key or value.

Returning the result variable instead of memo value.

Store the computed result in memo[n] and return it to reuse later.

5fill in blank

hard

Fill all three blanks to complete the memoized Fibonacci function.

DSA Go

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

Drag options to blanks, or click blank then click option'

An

Bresult

Cval

Dmemo

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong keys for memo map.

Storing or returning wrong variables.

The function checks if n is in memo, returns it if yes, otherwise computes result, stores it in memo[n], and returns it.

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