Overlapping Subproblems and Optimal Substructure in DSA Typescript - Build from Scratch

Understanding Overlapping Subproblems and Optimal Substructure with Fibonacci

📖 Scenario: Imagine you want to find the number of ways to climb stairs where you can take 1 or 2 steps at a time. This is a classic problem that can be solved using the Fibonacci sequence. To solve it efficiently, we use the ideas of overlapping subproblems and optimal substructure.

🎯 Goal: You will build a simple program to calculate Fibonacci numbers using a technique that remembers past answers to avoid repeated work. This shows how overlapping subproblems and optimal substructure help in solving problems efficiently.

📋 What You'll Learn

Create an array to store Fibonacci numbers for reuse

Set up a variable for the number of steps to climb

Write a function that uses stored results to calculate Fibonacci numbers

Print the Fibonacci number for the given steps

💡 Why This Matters

🌍 Real World

Many problems like calculating paths, costs, or sequences can be solved efficiently by remembering past answers and building solutions from smaller parts.

💼 Career

Understanding overlapping subproblems and optimal substructure is key for roles in software development, data science, and algorithm design where efficient problem solving is required.

1

Create the Fibonacci cache array

Create an array called fibCache with 11 elements, all initialized to -1.

DSA Typescript

# Your code here

Hint

Use new Array(11).fill(-1) to create an array of length 11 filled with -1.

2

Set the number of steps

Create a variable called steps and set it to 10.

DSA Typescript

const fibCache: number[] = new Array(11).fill(-1);
# Your code here

Hint

Use const steps: number = 10; to set the number of steps.

3

Write the Fibonacci function with memoization

Write a function called fib that takes a number n and returns the Fibonacci number using fibCache to store and reuse results. Use these rules:
- If n is 0 or 1, return 1.
- If fibCache[n] is not -1, return fibCache[n].
- Otherwise, calculate fib(n-1) + fib(n-2), store it in fibCache[n], and return it.

DSA Typescript

const fibCache: number[] = new Array(11).fill(-1);
const steps: number = 10;

# Your code here

Hint

Use a function with base cases for 0 and 1, check cache before computing, and store results in fibCache.

4

Print the Fibonacci number for the steps

Write a console.log statement to print the result of fib(steps).

DSA Typescript

const fibCache: number[] = new Array(11).fill(-1);
const steps: number = 10;

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

# Your code here

Hint

Use console.log(fib(steps)); to print the Fibonacci number for 10 steps.