Memoization Top Down DP in DSA Typescript - Build from Scratch

Memoization Top Down DP

📖 Scenario: You are helping a friend who wants to find the number of ways to climb stairs. Each time, they can climb either 1 or 2 steps. They want to know how many different ways they can reach the top if the staircase has a certain number of steps.

🎯 Goal: Build a program using memoization (top-down dynamic programming) to efficiently calculate the number of ways to climb a staircase with n steps.

📋 What You'll Learn

Create a function called climbStairs that takes a number n as input.

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

Implement the recursive logic with memoization to avoid repeated calculations.

Print the number of ways to climb n steps.

💡 Why This Matters

🌍 Real World

Calculating ways to climb stairs is a classic example of counting problems in real life, such as counting paths, combinations, or sequences.

💼 Career

Memoization and dynamic programming are important skills for software engineers to optimize recursive algorithms and improve performance in coding interviews and real projects.

1

Create the memo object

Create an empty object called memo to store previously calculated results.

DSA Typescript

// Your code here
// Create an empty object called memo

Hint

Use const memo: { [key: number]: number } = {}; to create an empty object for memoization.

2

Create the climbStairs function

Create a function called climbStairs that takes a number n as input.

DSA Typescript

const memo: { [key: number]: number } = {};

// Your code here
// Create function climbStairs with parameter n

Hint

Define the function with function climbStairs(n: number): number {}.

3

Add memoization and recursive logic

Inside climbStairs, add these steps:
1. If n is 0 or 1, return 1.
2. If memo[n] exists, return memo[n].
3. Otherwise, calculate climbStairs(n - 1) + climbStairs(n - 2), store it in memo[n], and return it.

DSA Typescript

const memo: { [key: number]: number } = {};

function climbStairs(n: number): number {
    // Your code here
}

Hint

Use base cases for 0 and 1 steps, check memo before recursion, and store results in memo.

4

Print the result for n = 5

Call climbStairs with n = 5 and print the result using console.log.

DSA Typescript

const memo: { [key: number]: number } = {};

function climbStairs(n: number): number {
    if (n === 0 || n === 1) {
        return 1;
    }
    if (memo[n] !== undefined) {
        return memo[n];
    }
    memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return memo[n];
}

// Your code here
// Call climbStairs with 5 and print the result

Hint

Use console.log(climbStairs(5)); to print the number of ways.