CodeBlanks Logo Icon CodeBlanks
Login Register

Summary - Memoization

Call memoized Fibonacci and print the result in a mini task.

Summary - Memoization

Memoization is the caching technique that prevents recomputation in recursive solutions. It drops complexity from exponential to polynomial.

In this mini task you will call memoized Fibonacci and print the result; combine all steps.

Memoization is the top-down form of dynamic programming; recursion + cache.

Practice Print memoized Fibonacci

Write fib_memo_print(n). Call fib_memo(n, {}) and print with print(). Output of fib_memo_print(15): 610.

Starter code

solution.py
def fib_memo_print(n):
    # Print memoized Fibonacci

Sample solution

solution.py
def fib_memo_print(n):
    # Print memoized Fibonacci
    def fib_memo(n, memo):
        if n in memo:
            return memo[n]
        if n <= 1:
            return n
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
        return memo[n]
    print(fib_memo(n, {}))
fib_memo_print(15)

Expected output

610

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Summary - Memoization: match the terms

Term Meaning
memoization Cache
dict Dictionary
recursion Self-call
cache Fast

2 Base condition

Question 
if n <= ____:
Answer 
if n <= 1:

Explanation: 1 is right.

3 Memoization is part of which technique?

  • Divide and conquer
  • Greedy
  • Dynamic programming Correct answer
  • Backtracking

Explanation: Dynamic programming.

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4