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.

Practice

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

easy

A. To reduce the memory usage by deleting variables

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.

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 caches answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting
• Thinking memoization reduces memory by deleting variables
• Believing memoization converts recursion to iteration

2. Which of the following is the correct TypeScript syntax to declare a memo object for caching number results indexed by number keys?

easy

A. const memo: Record = {};

B. const memo: Array<number> = [];

C. const memo: Map = new Map();

D. const memo: Set<number> = new Set();

Solution

1. Step 1: Identify memo type for number keys and values

   Memo should map number keys to number values, so Record fits.

2. Step 2: Check other options

   Array is indexed by number but not key-value pairs; Map uses string keys here; Set stores unique values, not key-value pairs.

3. Final Answer:

   const memo: Record = {}; -> Option A

4. Quick Check:

   Memo object with number keys and values = Record [OK]

Hint: Use Record for number-keyed memo objects [OK]

Common Mistakes:

• Using Map with wrong key/value types
• Using Set which stores only values, not key-value pairs
• Using Array when keys are not continuous indexes

3. Consider the following TypeScript code using memoization for Fibonacci numbers:

function fib(n: number, memo: Record = {}): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

What is the output of this code?

medium

A. Undefined

B. 5

C. 3

D. 8

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), fib(2) = fib(1) + fib(0). Values: fib(0)=0, fib(1)=1.

2. Step 2: Calculate values bottom-up

   fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Forgetting base cases fib(0)=0 and fib(1)=1
• Assuming memo[n] is undefined for n=1

4. The following TypeScript function attempts to use memoization for factorial calculation but has a bug:

function factorial(n: number, memo: Record = {}): number {
  if (n === 0) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1, memo);
  return memo[n];
}

What is the bug in this code?

medium

A. It incorrectly checks memo[n] which fails for factorial(0)

B. It does not handle the base case correctly

C. It uses the wrong multiplication operator

D. It does not pass memo object in recursive calls

Solution

1. Step 1: Analyze memo[n] check for zero value

   When n=0, factorial is 1, but memo[0] is undefined initially. The check if(memo[n]) fails for memo[0] = 0 or 1 because 0 or 1 are falsy/truthy but memo[0] might be undefined.

2. Step 2: Identify correct memo check

   Checking if(memo[n]) fails if memo[n] is 0 or falsy. Should check if(n in memo) instead to detect cached values correctly.

3. Final Answer:

   It incorrectly checks memo[n] which fails for factorial(0) -> Option A

4. Quick Check:

   Check memo keys with 'in' operator, not truthy check [OK]

Hint: Use 'n in memo' to check cache, not 'if(memo[n])' [OK]

Common Mistakes:

• Assuming memo[n] check works for zero or falsy values
• Missing base case for n=0
• Not passing memo in recursive calls

5. You want to optimize a function that counts the number of ways to climb n stairs taking 1 or 2 steps at a time using top-down memoization. Which of the following TypeScript implementations correctly applies memoization to avoid repeated calculations?

hard

A. function climbStairs(n: number, memo: Record = {}): number {
if (n <= 1) return 1;
if (memo[n]) return memo[n];
memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
return memo[n];
}

B. function climbStairs(n: number): number {
if (n <= 1) return 1;
return climbStairs(n - 1) + climbStairs(n - 2);
}

C. function climbStairs(n: number, memo: Record = {}): number {
if (n <= 1) return 1;
if (memo[n] !== undefined) return memo[n];
memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
return memo[n];
}

D. function climbStairs(n: number, memo: Record = {}): number {
if (n <= 1) return 1;
if (memo[n] === 0) return memo[n];
memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
return memo[n];
}

Solution

1. Step 1: Check memoization condition correctness

   function climbStairs(n: number, memo: Record = {}): number { if (n <= 1) return 1; if (memo[n] !== undefined) return memo[n]; memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo); return memo[n]; } uses 'memo[n] !== undefined' to check cache, which correctly handles zero or falsy values.

2. Step 2: Compare other options

   function climbStairs(n: number, memo: Record = {}): number { if (n <= 1) return 1; if (memo[n]) return memo[n]; memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo); return memo[n]; } uses 'if(memo[n])' which fails if memo[n] is 0; function climbStairs(n: number): number { if (n <= 1) return 1; return climbStairs(n - 1) + climbStairs(n - 2); } has no memoization; function climbStairs(n: number, memo: Record = {}): number { if (n <= 1) return 1; if (memo[n] === 0) return memo[n]; memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo); return memo[n]; } checks 'memo[n] === 0' which misses other cached values.

3. Final Answer:

   Option C correctly applies memoization with proper cache check -> Option C

4. Quick Check:

   Use '!== undefined' to check memo cache [OK]

Hint: Check cache with '!== undefined' to handle all values [OK]

Common Mistakes:

• Using 'if(memo[n])' which fails for zero values
• Not passing memo in recursive calls
• Not using memoization at all