Memoization Top Down DP in DSA Python - Build from Scratch

Memoization with Top Down Dynamic Programming

📖 Scenario: Imagine you want to find the number of ways to climb a staircase with 5 steps. You can climb either 1 step or 2 steps at a time. Calculating this directly can repeat the same calculations many times.We will use a technique called memoization to remember answers we already found, so we don't repeat work.

🎯 Goal: Build a program that uses memoization with top down dynamic programming to find the number of ways to climb 5 steps.

📋 What You'll Learn

Create a function called count_ways that takes a step number.

Use a dictionary called memo to store results of steps already calculated.

Use recursion with memoization to find the number of ways to reach the top.

Print the number of ways to climb 5 steps.

💡 Why This Matters

🌍 Real World

Memoization helps speed up programs that solve problems with overlapping subproblems, like calculating Fibonacci numbers, pathfinding, or resource allocation.

💼 Career

Understanding memoization and dynamic programming is important for software engineers to write efficient code and solve complex algorithm problems in interviews and real projects.

1

Create the memo dictionary

Create an empty dictionary called memo to store results of steps already calculated.

DSA Python

# Create an empty dictionary called memo
# Your code here

Hint

Use memo = {} to create an empty dictionary.

2

Define the count_ways function

Define a function called count_ways that takes a parameter step. Inside the function, if step is 0 or 1, return 1. This is the base case for climbing stairs.

DSA Python

memo = {}
# Define the count_ways function with parameter step
# Your code here

Hint

Base cases: 1 way to climb 0 or 1 step.

3

Add memoization and recursion

Inside count_ways, check if step is in memo. If yes, return memo[step]. Otherwise, calculate the number of ways by calling count_ways(step - 1) plus count_ways(step - 2). Store this result in memo[step] and return it.

DSA Python

memo = {}
def count_ways(step):
    if step == 0 or step == 1:
        return 1
    # Add memoization check and recursive calls
    # Your code here

Hint

Use memo to save and reuse results to avoid repeated work.

4

Print the number of ways to climb 5 steps

Call count_ways with argument 5 and print the result.

DSA Python

memo = {}
def count_ways(step):
    if step == 0 or step == 1:
        return 1
    if step in memo:
        return memo[step]
    memo[step] = count_ways(step - 1) + count_ways(step - 2)
    return memo[step]

# Print the number of ways to climb 5 steps
# Your code here

Hint

Print the result of count_ways(5).

Practice

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

easy

A. To store results of subproblems to avoid repeated calculations

B. To sort the input data before processing

C. To convert recursive code into iterative code

D. To increase the size of the input for better accuracy

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 describes this purpose correctly. Other options describe unrelated actions.

3. Final Answer:

   To store results of subproblems to avoid repeated calculations -> Option A

4. Quick Check:

   Memoization = Store subproblem results [OK]

Hint: Memoization means saving answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting or iteration
• Thinking memoization increases input size
• Believing memoization converts recursion to iteration

2. Which of the following is the correct way to define a memo dictionary in Python for top-down DP?

easy

A. memo = []

B. memo = {}

C. memo = set()

D. memo = ()

Solution

1. Step 1: Identify data structure for memo

   Memoization requires a dictionary to store key-value pairs of subproblem inputs and results.

2. Step 2: Match with options

   Only memo = {} uses a dictionary ({}). Lists, sets, and tuples do not support key-value storage.

3. Final Answer:

   memo = {} -> Option B

4. Quick Check:

   Memo dictionary = {} [OK]

Hint: Use {} for memo dictionary in Python [OK]

Common Mistakes:

• Using list or set instead of dictionary
• Confusing tuple with dictionary
• Not initializing memo before recursion

3. What will be the output of the following code?

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))

medium

A. 3

B. 8

C. 5

D. Error

Solution

1. Step 1: Understand Fibonacci calculation with memo

   fib(5) calculates Fibonacci number at position 5 using memo to save results.

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 C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Fibonacci(5) = 5 using memoized recursion [OK]

Common Mistakes:

• Confusing Fibonacci sequence values
• Expecting 8 instead of 5 for fib(5)
• Thinking code causes error due to default dict

4. Identify the error in this memoized Fibonacci function:

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

medium

A. Missing base case for n=0

B. Function lacks return statement

C. Memo dictionary is not used correctly

D. Default mutable argument causes shared state across calls

Solution

1. Step 1: Analyze default argument usage

   Using memo={} as default argument creates shared dictionary across calls, causing unexpected behavior.

2. Step 2: Identify correct practice

   Default mutable arguments should be avoided; better to use None and initialize inside function.

3. Final Answer:

   Default mutable argument causes shared state across calls -> Option D

4. Quick Check:

   Mutable default argument = bug [OK]

Hint: Avoid mutable default args like {} in function definitions [OK]

Common Mistakes:

• Ignoring mutable default argument issue
• Thinking base case is missing
• Assuming memo dictionary usage is wrong

5. You want to find the number of ways to climb a staircase of n steps, taking 1 or 2 steps at a time. Which memoized top-down function correctly solves this problem?

hard

A. def climb(n, memo=None):
if memo is None:
memo = {}
if n < 0:
return 0
if n == 0:
return 1
if n in memo:
return memo[n]
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]

B. def climb(n):
if n <= 1:
return n
return climb(n-1) + climb(n-2)

C. def climb(n, memo={}):
if n == 0:
return 0
if n in memo:
return memo[n]
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]

D. def climb(n, memo=None):
if memo is None:
memo = []
if n <= 1:
return 1
if n in memo:
return memo[n]
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]

Solution

1. Step 1: Understand problem and base cases

   Number of ways to climb n steps with 1 or 2 steps is classic DP with base cases: ways(0)=1, ways(-1)=0.

2. Step 2: Check each option for correctness

   def climb(n, memo=None): if memo is None: memo = {} if n < 0: return 0 if n == 0: return 1 if n in memo: return memo[n] memo[n] = climb(n-1, memo) + climb(n-2, memo) return memo[n] correctly initializes memo, handles negative and zero cases, and uses memoization properly. Others have wrong base cases or memo usage.

3. Final Answer:

   Option A function correctly solves the problem -> Option A

4. Quick Check:

   Proper base cases + memo dict = correct solution [OK]

Hint: Base cases and memo dict initialization are key [OK]

Common Mistakes:

• Wrong base case returns
• Using mutable default memo argument
• Using list instead of dict for memo