Pattern #12 — Dynamic Programming (DP) 🧠

Pattern #12 — Dynamic Programming (DP) 🧠

People fear DP. Don't. At its heart it's one tiny idea: don't solve the same small problem twice — remember the answer. That's it.

1. The Idea (in one line)

Break a big problem into smaller sub-problems, solve each ONCE, and reuse (remember) the answers.

   Real-life analogy 📝
   ────────────────────
   You're climbing stairs and someone asks "how many ways to
   reach step 10?" You realize: ways(10) = ways(9) + ways(8).
   And ways(9) needs ways(8) too. Instead of recomputing ways(8)
   again and again, you write it on a sticky note the first time.
   Next time you need it → just read the note. 🎯

   That sticky note is called MEMOIZATION.

2. The Classic Example — Fibonacci

   fib(n) = fib(n-1) + fib(n-2)

   WITHOUT DP (recompute everything) — SLOW:
                    fib(5)
                 /         \
             fib(4)        fib(3)
            /    \         /    \
        fib(3) fib(2)   fib(2) fib(1)
        ...  fib(3) computed TWICE, fib(2) THREE times! 😱
        → exponential time. Terrible.

   WITH DP (remember each answer) — FAST:
   fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5
   Each computed ONCE, read from memory after. → O(n). 🚀

3. Two Ways to Do DP

   A) TOP-DOWN (Memoization) 📥
      Write the natural recursion, but cache each answer.
      "Solve big by asking for smaller, remember as you go."

   B) BOTTOM-UP (Tabulation) 📤
      Build a table from the smallest cases upward.
      "Fill dp[0], dp[1], dp[2]... until dp[n]."

   Both give the same answer. Top-down is easier to write;
   bottom-up is often a bit faster and avoids deep recursion.

4. 🔍 How to SPOT This Pattern

   Use DP when you see:
   ✅ "count the number of ways ..."
   ✅ "minimum / maximum cost / path / length ..."
   ✅ "can you reach / make / partition ..."
   ✅ The problem breaks into smaller SAME-shaped sub-problems
      that OVERLAP (you'd solve the same thing repeatedly).
   ✅ Greedy gives a wrong answer (so you need to consider options).

5. The 3 Questions to Crack Any DP

   1. STATE:  what does dp[i] MEAN?
      e.g. "dp[i] = number of ways to reach step i"

   2. TRANSITION: how does dp[i] use smaller answers?
      e.g. "dp[i] = dp[i-1] + dp[i-2]"

   3. BASE CASE: the smallest known answers.
      e.g. "dp[0] = 1, dp[1] = 1"

   Get these three right and the code writes itself.

6. The Code Templates 📝

   // A) Top-down (memoization) — Climbing Stairs
   function climb(n, memo = {}) {
     if (n <= 2) return n;                 // base case
     if (memo[n]) return memo[n];          // read the sticky note
     memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
     return memo[n];
   }

   // B) Bottom-up (tabulation) — Climbing Stairs
   function climbTable(n) {
     if (n <= 2) return n;
     const dp = [0, 1, 2];                 // base cases
     for (let i = 3; i <= n; i++)
       dp[i] = dp[i - 1] + dp[i - 2];      // transition
     return dp[n];
   }

7. Practice Problems (in a good learning order)

   ⭐ START HERE (1D DP)
   • Climbing Stairs
   • House Robber
   • Maximum Subarray (Kadane's)
   • Coin Change

   ⭐⭐ Next (2D DP / strings)
   • Unique Paths (grid)
   • Longest Common Subsequence
   • 0/1 Knapsack
   • Edit Distance
   • Longest Increasing Subsequence

8. ⚠️ Common Mistake

   ❌ Jumping to code before defining the STATE. If you can't say
      "dp[i] means ___" in one sentence, you're not ready to code.
   ❌ Wrong base cases → the whole table is off by a bit.

Key Takeaway

   DP = recursion + memory. Break into overlapping sub-problems,
   solve each once, remember it. Crack any DP with 3 questions:
   State, Transition, Base case. It's not scary — it's just
   "don't repeat work".

Next: Pattern #13 — Cyclic Sort, a neat trick for arrays holding numbers 1..n. 🔁