Memoization Top Down DP in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of dynamic programming?

Memoization is a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. It helps avoid repeated calculations.

beginner

How does top-down dynamic programming differ from bottom-up?

Top-down DP uses recursion with memoization to solve problems by breaking them into smaller subproblems and caching results. Bottom-up DP solves smaller subproblems first and builds up to the solution iteratively.

intermediate

In JavaScript, how can you implement memoization for a recursive function?

You can use an object or Map to store results keyed by input parameters. Before computing, check if the result exists in the cache. If yes, return it; otherwise, compute and store it.

beginner

Why is memoization useful in solving the Fibonacci sequence recursively?

Without memoization, Fibonacci recursion repeats calculations exponentially. Memoization stores results of each Fibonacci number once, reducing time complexity from exponential to linear.

intermediate

What is a common pitfall when using memoization in top-down DP?

A common pitfall is not properly caching results for all unique input states, which leads to repeated calculations and defeats the purpose of memoization.

What does memoization primarily help to reduce in recursive algorithms?

A Code length

B Memory usage

C Repeated calculations

D Input size

Memoization stores results of subproblems to avoid recalculating them, reducing repeated calculations.

Which data structure is commonly used in JavaScript to store memoized results?

A Object or Map

B Array

C Set

D Queue

Objects or Maps are used to store key-value pairs of input parameters and their results.

In top-down DP, when do you check the memoization cache?

A After computing the result

B Before computing the result

C Only at the end of recursion

D Never

You check the cache before computing to reuse stored results and avoid redundant work.

What is the time complexity of Fibonacci with memoization compared to plain recursion?

A Exponential vs linear

B Linear vs quadratic

C Quadratic vs linear

D Linear vs exponential

Plain recursion is exponential; memoization reduces it to linear time.

Which of these is NOT a benefit of memoization?

A Lower memory usage

B Reduced repeated work

C Faster execution

D Simpler code logic

Memoization uses extra memory to store results, so it does not reduce memory usage.

Explain how memoization works in top-down dynamic programming with an example.

Think about how you remember answers to avoid repeating work.

Describe the difference between top-down and bottom-up dynamic programming approaches.

Consider how you start solving the problem in each approach.

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