Why Overlapping Subproblems and Optimal Substructure in DSA Typescript?

The Big Idea

What if you could solve big problems by solving small parts just once and reusing the answers?

The Scenario

Imagine you are solving a big puzzle by hand, and you keep solving the same small parts over and over again without remembering the answers.

The Problem

This manual way wastes time and effort because you redo the same work many times, making the whole process slow and frustrating.

The Solution

By recognizing overlapping subproblems and using optimal substructure, you can solve each small part once, save the answer, and reuse it to build the final solution quickly and efficiently.

Before vs After

✗ Before

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

✓ After

function fib(n: number, memo: number[] = []): number {
  if (memo[n] !== undefined) return memo[n];
  if (n <= 1) return n;
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

What It Enables

This concept enables solving complex problems efficiently by breaking them into smaller, reusable parts.

Real Life Example

Planning the fastest route on a map by remembering the shortest paths between cities you already calculated instead of recalculating them every time.

Key Takeaways

Manual repetition wastes time and effort.

Overlapping subproblems means solving the same small problem multiple times.

Optimal substructure means the best solution can be built from best solutions of smaller parts.