Memoization Top Down DP in DSA Javascript

Mental Model

Remember answers to smaller 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 work every time.

problem -> solve smaller problem -> store answer in memory
          ↑                             ↓
       check memory ← if answer exists, use it

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using memoization

Goal: Find fib(5) efficiently by storing results of fib(0) to fib(5)

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

memo = {}
Call stack: fib(5)

Why: Start solving the big problem

Step 2: Call fib(4) inside fib(5), no memo for 4

memo = {}
Call stack: fib(5) -> fib(4)

Why: Need fib(4) to find fib(5)

Step 3: Call fib(3) inside fib(4), no memo for 3

memo = {}
Call stack: fib(5) -> fib(4) -> fib(3)

Why: Need fib(3) to find fib(4)

Step 4: Call fib(2) inside fib(3), no memo for 2

memo = {}
Call stack: fib(5) -> fib(4) -> fib(3) -> fib(2)

Why: Need fib(2) to find fib(3)

Step 5: Call fib(1) inside fib(2), base case returns 1

memo = {}
Call stack: fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1)

Why: Base case reached

Step 6: Call fib(0) inside fib(2), base case returns 0

memo = {}
Call stack: fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(0)

Why: Base case reached

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

memo = {2:1}
Call stack: fib(5) -> fib(4) -> fib(3)

Why: Save result to avoid future recalculation

Step 8: Call fib(1) inside fib(3), base case returns 1

memo = {2:1}
Call stack: fib(5) -> fib(4) -> fib(3) -> fib(1)

Why: Base case reached

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

memo = {2:1, 3:2}
Call stack: fib(5) -> fib(4)

Why: Save result

Step 10: Call fib(2) inside fib(4), found in memo as 1

memo = {2:1, 3:2}
Call stack: fib(5) -> fib(4) -> fib(2)

Why: Reuse stored answer

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

memo = {2:1, 3:2, 4:3}
Call stack: fib(5)

Why: Save result

Step 12: Call fib(3) inside fib(5), found in memo as 2

memo = {2:1, 3:2, 4:3}
Call stack: fib(5) -> fib(3)

Why: Reuse stored answer

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

memo = {2:1, 3:2, 4:3, 5:5}
Call stack: empty

Why: Final answer stored

Result:

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

Annotated Code

DSA Javascript

class Fibonacci {
  constructor() {
    this.memo = {};
  }

  fib(n) {
    if (n <= 1) return n; // base case
    if (this.memo[n] !== undefined) return this.memo[n]; // reuse stored answer

    // calculate fib(n-1) and fib(n-2) recursively
    const result = this.fib(n - 1) + this.fib(n - 2);
    this.memo[n] = result; // store result for future
    return result;
  }
}

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

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

return base Fibonacci values 0 or 1

if (this.memo[n] !== undefined) return this.memo[n]; // reuse stored answer

check if answer already computed to avoid repeat work

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

recursively compute smaller subproblems

this.memo[n] = result; // store result for future

save computed result for memoization

Output

fib(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 object storing results and call stack depth

vs Alternative: Compared to naive recursion with O(2^n) time, memoization reduces repeated work drastically to linear time

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA Javascript

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

n = 1 (smallest non-zero input)

Returns 1 immediately as base case

DSA Javascript

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

Repeated calls with same n

Returns stored answer from memo without recomputation

DSA Javascript

if (this.memo[n] !== undefined) return this.memo[n]; // reuse stored answer

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 store and reuse answers.

Common Mistakes

Mistake: Not checking memo before recursive calls, causing repeated work
Fix: Add memo check before recursion to return stored results immediately

Mistake: Not storing computed results in memo after recursion
Fix: Store the computed result in memo before returning

Summary

Stores answers to smaller problems to avoid repeated work in recursion.

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

The key is to check and save answers in a memory structure before and after recursion.

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 reduce the memory usage by deleting variables

Solution

1. Step 1: Understand memoization concept

   Memoization saves the results of expensive function calls and returns the cached result when the same inputs occur again.

2. Step 2: Identify its role in top-down DP

   In top-down dynamic programming, memoization prevents repeated calculations of the same subproblems by storing their results.

3. Final Answer:

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

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 usage
• Believing memoization converts recursion to iteration

2. Which of the following is the correct way to declare a memo object in JavaScript for top-down DP?

easy

A. const memo = 0;

B. let memo = [];

C. const memo = new Map();

D. var memo = function() {};

Solution

1. Step 1: Identify memo storage type

   Memoization requires a data structure to store key-value pairs of subproblem results. Map is ideal for this in JavaScript.

2. Step 2: Check options for correct syntax

   const memo = new Map(); uses new Map() which is correct. let memo = []; is an array, which can work but less flexible. var memo = function() {}; is a function, incorrect. const memo = 0; is a number, incorrect.

3. Final Answer:

   const memo = new Map(); -> Option C

4. Quick Check:

   Memo object = Map() [OK]

Hint: Use Map() for flexible memo keys [OK]

Common Mistakes:

• Using a function instead of an object
• Initializing memo as a number
• Confusing array with Map for memo

3. What will be the output of the following JavaScript code using memoization for Fibonacci?

const memo = new Map();
function fib(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n - 1) + fib(n - 2);
  memo.set(n, result);
  return result;
}
console.log(fib(5));

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci sequence

   Fibonacci sequence starts as 0,1,1,2,3,5,8,... So fib(5) = 5.

2. Step 2: Trace the code execution

   The function uses memoization to avoid repeated calls. fib(5) calculates fib(4)+fib(3), and so on, finally returning 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence values [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring base cases
• Not understanding memo usage

4. Identify the bug in this memoized factorial function and select the fix:

const memo = {};
function factorial(n) {
  if (n === 0) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1);
  return memo[n];
}
console.log(factorial(5));

medium

A. Change base case to 'if (n === 1) return 1;'

B. Change 'if (memo[n])' to 'if (memo.hasOwnProperty(n))'

C. Initialize memo as 'const memo = new Map();'

D. Remove memo and use plain recursion

Solution

1. Step 1: Understand the bug in memo check

   Using 'if (memo[n])' fails when memo[n] is 0 or falsy. It should check if the key exists.

2. Step 2: Fix by checking key existence

   Using 'memo.hasOwnProperty(n)' correctly checks if the result is stored, avoiding false negatives.

3. Final Answer:

   Change 'if (memo[n])' to 'if (memo.hasOwnProperty(n))' -> Option B

4. Quick Check:

   Check key existence, not truthiness [OK]

Hint: Check key presence, not value truthiness [OK]

Common Mistakes:

• Checking memo[n] directly causes bugs for 0 or falsy values
• Changing base case unnecessarily
• Removing memo defeats purpose

5. Given the following top-down memoized function to count ways to climb stairs, what is the output of countWays(4)?

const memo = {};
function countWays(n) {
  if (n === 0) return 1;
  if (n < 0) return 0;
  if (memo.hasOwnProperty(n)) return memo[n];
  memo[n] = countWays(n - 1) + countWays(n - 2);
  return memo[n];
}
console.log(countWays(4));

hard

A. 7

B. 6

C. 8

D. 5

Solution

1. Step 1: Understand the problem

   This function counts ways to climb stairs taking 1 or 2 steps. Base cases: countWays(0)=1, countWays(negative)=0.

2. Step 2: Calculate countWays(4) step-by-step

   countWays(4) = countWays(3) + countWays(2) countWays(3) = countWays(2) + countWays(1) countWays(2) = countWays(1) + countWays(0) countWays(1) = countWays(0) + countWays(-1) countWays(0) = 1, countWays(-1) = 0 So countWays(1) = 1 + 0 = 1 countWays(2) = 1 + 1 = 2 countWays(3) = 2 + 1 = 3 countWays(4) = 3 + 2 = 5

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Ways to climb 4 stairs = 5 [OK]

Hint: Count ways as sum of previous two counts [OK]

Common Mistakes:

• Miscounting base cases
• Forgetting negative input returns 0
• Mixing up addition order