Why Memoization Top Down DP in DSA Go?

The Big Idea

What if you could solve tough problems instantly by remembering past answers?

The Scenario

Imagine you want to find the number of ways to climb stairs, but you try every possible step combination by hand or simple code that repeats the same calculations many times.

The Problem

This manual method wastes a lot of time recalculating the same answers over and over. It's like solving the same puzzle repeatedly without remembering the solution you found before.

The Solution

Memoization stores the answers to smaller problems as you solve them. When you need the answer again, you just look it up instead of recalculating, saving time and effort.

Before vs After

✗ Before

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    return climbStairs(n-1) + climbStairs(n-2)
}

✓ After

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

What It Enables

It makes solving complex problems fast and efficient by remembering past results.

Real Life Example

Calculating the fastest route in a map app where many paths overlap, so the app remembers parts of routes it already checked.

Key Takeaways

Manual repeated calculations waste time and resources.

Memoization saves results to avoid repeated work.

Top Down DP with memoization speeds up recursive solutions.

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