Memoization Top Down DP in DSA Typescript

Mental Model

Remember answers to small problems so you don't solve them again.

Analogy: Like writing down answers to tricky homework questions so you can check them later instead of redoing the whole problem.

Start: problem -> break into smaller problems -> solve smaller problems -> remember answers -> combine answers -> final answer

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using memoization top down DP

Goal: Find the 5th Fibonacci number efficiently by storing results of smaller Fibonacci calls

Step 1: Call fib(5), no memo yet

memo = {}
fib(5) -> calls fib(4) and fib(3)

Why: We start by breaking the problem into smaller parts

Step 2: Call fib(4), no memo yet

memo = {}
fib(4) -> calls fib(3) and fib(2)

Why: Keep breaking down until base cases

Step 3: Call fib(3), no memo yet

memo = {}
fib(3) -> calls fib(2) and fib(1)

Why: Keep breaking down until base cases

Step 4: Call fib(2), no memo yet

memo = {}
fib(2) -> calls fib(1) and fib(0)

Why: Keep breaking down until base cases

Step 5: fib(1) and fib(0) are base cases, return 1 and 0

memo = {}
fib(1)=1, fib(0)=0

Why: Base cases stop recursion

Step 6: Calculate fib(2) = fib(1)+fib(0) = 1+0=1, store in memo

memo = {2:1}

Why: Store result to avoid recalculating

Step 7: Calculate fib(3) = fib(2)+fib(1) = 1+1=2, store in memo

memo = {2:1, 3:2}

Why: Use memoized fib(2) to save work

Step 8: Calculate fib(4) = fib(3)+fib(2) = 2+1=3, store in memo

memo = {2:1, 3:2, 4:3}

Why: Use memoized values to combine results

Step 9: Calculate fib(5) = fib(4)+fib(3) = 3+2=5, store in memo

memo = {2:1, 3:2, 4:3, 5:5}

Why: Final answer computed using stored results

Result:

memo = {2:1, 3:2, 4:3, 5:5}
Final answer: 5

Annotated Code

DSA Typescript

class Fibonacci {
  memo: Map<number, number>;

  constructor() {
    this.memo = new Map();
  }

  fib(n: number): number {
    if (n <= 1) return n; // base case

    if (this.memo.has(n)) {
      return this.memo.get(n)!; // return stored result
    }

    const result = this.fib(n - 1) + this.fib(n - 2); // recursive calls
    this.memo.set(n, result); // store result
    return result;
  }
}

const fibCalc = new Fibonacci();
const n = 5;
console.log(`Fibonacci(${n}) = ${fibCalc.fib(n)}`);

if (n <= 1) return n; // base case

Stop recursion when n is 0 or 1

if (this.memo.has(n)) { return this.memo.get(n)!; // return stored result }

Return memoized answer if available to avoid recomputation

const result = this.fib(n - 1) + this.fib(n - 2); // recursive calls

Break problem into smaller subproblems

this.memo.set(n, result); // store result

Save computed result for future calls

Output

Fibonacci(5) = 5

Complexity Analysis

Time: O(n) because each number from 0 to n is computed once and stored

Space: O(n) for the memo storage and recursion call stack

vs Alternative: Compared to naive recursion which is O(2^n), memoization drastically reduces repeated work

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Typescript

if (n <= 1) return n; // base case

n = 1

Returns 1 immediately as base case

DSA Typescript

if (n <= 1) return n; // base case

Repeated calls with same n

Returns memoized result without recomputation

DSA Typescript

if (this.memo.has(n)) { return this.memo.get(n)!; }

When to Use This Pattern

When a problem asks for a value defined by smaller subproblems and has overlapping calls, use memoization top down DP to save repeated work.

Common Mistakes

Mistake: Not storing the computed result before returning it
Fix: Add memo.set(n, result) before returning to save the answer

Mistake: Not checking memo before recursive calls
Fix: Check if result exists in memo and return it early to avoid duplicate work

Summary

Stores answers to subproblems to avoid repeated calculations in recursive solutions.

Use when a problem can be broken into overlapping smaller problems solved recursively.

Remember to check memo before recursion and store results after computing.