🗓️ Day 18: Memoization & Dynamic Programming (DP) Introduction

📘 What You’ll Learn

What is memoization?
What is dynamic programming (DP)?
The difference between Top-Down and Bottom-Up approaches
When to use DP
Visualize with Fibonacci Tree
TypeScript implementations
LeetCode Homework with explanation

🧠 Concept

Memoization is like sticky notes for your brain. If you’ve already solved a subproblem, just reuse the answer. No need to do the same work twice. 🧾

Dynamic Programming (DP) is an optimization technique where problems are broken into overlapping subproblems and solved using their optimal substructure.

There are two styles:

Top-Down (Memoization): Recursive + cache
Bottom-Up (Tabulation): Iterative from base case

✅ When to Use DP?

The problem has overlapping subproblems
It has optimal substructure

Examples: Fibonacci, Climbing Stairs, House Robber, etc.

🔍 Visualization (Fibonacci Tree)

Calculating fib(5) without memoization:

                 fib(5)
               /      \
          fib(4)      fib(3)
         /     \      /    \
     fib(3)  fib(2)  fib(2)  fib(1)
     ...repeated subproblems...

Too many repeated calls 😫

With memoization:

We store results.
Save time and avoid recalculations. 🧠💡

💻 TypeScript Examples

❌ Brute-force Recursive (Slow!)

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

⏱️ Time: O(2ⁿ)
Repeats work unnecessarily

✅ Top-Down Memoization

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

console.log(fib(10)); // 55

⏱️ Time: O(n)
💾 Space: O(n) (call stack + memo)

✅ Bottom-Up Tabulation

function fibBottomUp(n: number): number {
  if (n <= 1) return n;
  const dp: number[] = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

console.log(fibBottomUp(10)); // 55

⏱️ Time: O(n)
💾 Space: O(n)

💡 Optimized Bottom-Up (Constant Space)

function fibOptimized(n: number): number {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

⏱️ Time: O(n)
💾 Space: O(1) 🚀

🧪 LeetCode Homework

📘 746. Min Cost Climbing Stairs

🧩 You are given an array where each index is a step and has a cost. You can climb either 1 or 2 steps at a time. Return the min cost to reach the top.

function minCostClimbingStairs(cost: number[]): number {
  const n = cost.length;
  const dp: number[] = new Array(n);
  dp[0] = cost[0];
  dp[1] = cost[1];
  for (let i = 2; i < n; i++) {
    dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
  }
  return Math.min(dp[n - 1], dp[n - 2]);
}

const cost = [10, 15, 20];
console.log(minCostClimbingStairs(cost)); // 15

📌 Key Takeaways

Use memoization when you notice repeat subcalls (top-down)
Use tabulation for better control and memory (bottom-up)
Recognize overlapping subproblems and optimal substructure
Mastering DP opens doors to many algorithm problems! 💥

🔮 Up Next

▶️ Day 19: House Robber Pattern