Memoization Top Down DP in DSA Javascript - Build from Scratch

Memoization with Top Down Dynamic Programming

📖 Scenario: Imagine you want to find the number of ways to climb a staircase with a certain number of steps. You can climb either 1 or 2 steps at a time. This is a common problem where repeated calculations happen. Using memoization helps us remember answers to smaller problems so we don't repeat work.

🎯 Goal: You will build a function that uses memoization (top down dynamic programming) to efficiently calculate the number of ways to climb n steps.

📋 What You'll Learn

Create a function called climbStairs that takes a number n.

Create a memo object called memo to store results of subproblems.

Use a helper function called countWays inside climbStairs that uses recursion and memoization.

Return the total number of ways to climb n steps.

Print the result of climbStairs(5).

💡 Why This Matters

🌍 Real World

Memoization helps in many real-world problems like calculating Fibonacci numbers, optimizing routes, or managing resources efficiently by avoiding repeated calculations.

💼 Career

Understanding memoization and dynamic programming is essential for software engineers to write efficient algorithms and solve complex problems in interviews and real projects.

1

Create the main function and memo object

Create a function called climbStairs that takes a parameter n. Inside it, create an empty object called memo to store results.

DSA Javascript

function climbStairs(n) {
  // Create an empty object called memo
  // Your code here
}

Hint

Think of memo as a notebook where you write down answers to smaller problems so you don't solve them again.

2

Add the recursive helper function with memoization

Inside climbStairs, create a helper function called countWays that takes a parameter step. Use if statements to return 1 if step is 0 or 1. If step is in memo, return memo[step]. Otherwise, set memo[step] to the sum of countWays(step - 1) and countWays(step - 2), then return memo[step].

DSA Javascript

function climbStairs(n) {
  const memo = {};

  // Create helper function countWays(step) with memoization
  // Your code here
}

Hint

Remember to check if the answer is already in memo before calculating it again.

3

Call the helper function and return the result

Inside climbStairs, after the countWays function, return the result of calling countWays(n).

DSA Javascript

function climbStairs(n) {
  const memo = {};

  function countWays(step) {
    if (step === 0 || step === 1) {
      return 1;
    }
    if (memo[step] !== undefined) {
      return memo[step];
    }
    memo[step] = countWays(step - 1) + countWays(step - 2);
    return memo[step];
  }

  // Return the result of countWays(n)
  // Your code here
}

Hint

Call the helper function with n and return its result.

4

Print the number of ways to climb 5 steps

Write a line to print the result of calling climbStairs(5).

DSA Javascript

function climbStairs(n) {
  const memo = {};

  function countWays(step) {
    if (step === 0 || step === 1) {
      return 1;
    }
    if (memo[step] !== undefined) {
      return memo[step];
    }
    memo[step] = countWays(step - 1) + countWays(step - 2);
    return memo[step];
  }

  return countWays(n);
}

// Print the number of ways to climb 5 steps
// Your code here

Hint

Use console.log(climbStairs(5)) to print the result.

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