Memoization (Top-Down DP)

DSA · Dynamic Programming

Theory

Memoization is a technique where a recursive function stores the result of each subproblem the first time it is computed, and returns the stored result when the same subproblem appears again. It turns exponential recursion into polynomial time whenever subproblems overlap. The classic example is Fibonacci: naive recursion recomputes fib(30) millions of times because fib(n) calls fib(n-1) and fib(n-2), which call the same values again. With a dictionary cache (or Python's functools.lru_cache), each value from 0 to n is computed once, so the time drops from O(2^n) to O(n). Memoization is called top-down dynamic programming because you start from the big problem and recurse down, filling the cache only for subproblems you actually need.

Why we use it

It is the easiest way to convert a correct but slow recursive solution into a fast one, often by adding a single decorator.

When to use it

Use memoization when a problem has a natural recursive definition with overlapping subproblems and you do not need every subproblem. Watch the recursion depth limit (about 1,000 in Python) for very deep problems.

How it works

  1. solve(state)
  2. State in memo? Yes: Return memo[state]. No: Compute from smaller states.
  3. Store result in memo
  4. Return result

Syntax

from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
    if base case: return value
    return combine(solve(smaller states))

Example

import time
from functools import lru_cache

calls = 0
def fib_slow(n):
    global calls
    calls += 1
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)

t = time.perf_counter()
print("slow fib(25) =", fib_slow(25), "calls:", calls)

memo = {}
def fib_memo(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]
print("memo fib(90) =", fib_memo(90), "cached values:", len(memo))

@lru_cache(maxsize=None)
def grid_paths(r, c):
    if r == 0 or c == 0:
        return 1
    return grid_paths(r - 1, c) + grid_paths(r, c - 1)
print("paths in 10x10 grid:", grid_paths(10, 10))
print(grid_paths.cache_info())

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic