Memoization Top Down DP in DSA Go - Build from Scratch

Memoization with Top Down Dynamic Programming

📖 Scenario: Imagine you are helping a farmer count the number of ways to climb a staircase with a certain number of steps. The farmer can climb either 1 or 2 steps at a time. You will write a program to find out how many different ways the farmer can reach the top.

🎯 Goal: Build a Go program that uses memoization with top down dynamic programming to efficiently calculate the number of ways to climb a staircase of n steps.

📋 What You'll Learn

Create a map called memo to store intermediate results

Create a recursive function called climbWays that takes an integer n and returns the number of ways to climb n steps

Use memoization inside climbWays to avoid repeated calculations

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world problems like calculating Fibonacci numbers, optimizing game moves, and solving complex puzzles efficiently.

💼 Career

Understanding memoization and dynamic programming is essential for software engineers to write efficient algorithms and solve optimization problems in interviews and real projects.

1

Create the memo map

Create a variable called memo as a map from int to int to store intermediate results.

DSA Go

package main

import "fmt"

func main() {
    // Create memo map here
}

Hint

Use make(map[int]int) to create the map.

2

Write the climbWays function

Write a recursive function called climbWays that takes an integer n and returns an int. If n is 0 or 1, return 1. Otherwise, return the sum of climbWays(n-1) and climbWays(n-2).

DSA Go

package main

import "fmt"

var memo map[int]int

func main() {
    memo = make(map[int]int)
}

// Write climbWays function here

Hint

Base cases return 1. Recursive calls add results for n-1 and n-2.

3

Add memoization to climbWays

Modify the climbWays function to use the memo map. First, check if n is in memo. If yes, return the stored value. Otherwise, compute the result, store it in memo[n], and then return it.

DSA Go

package main

import "fmt"

var memo map[int]int

func climbWays(n int) int {
    // Add memoization check here
}

func main() {
    memo = make(map[int]int)
}

Hint

Use val, ok := memo[n] to check if result is cached.

4

Print the number of ways to climb 5 steps

In the main function, print the result of climbWays(5).

DSA Go

package main

import "fmt"

var memo map[int]int

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

func main() {
    memo = make(map[int]int)
    // Print the number of ways to climb 5 steps
}

Hint

Use fmt.Println(climbWays(5)) to print the result.

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