Dynamic Programming (DP) is an optimization technique for solving problems that have Overlapping Subproblems and Optimal Substructure. It boils down to: "Those who do not remember the past are condemned to repeat it."

1. Memoization (Top-Down)

Think of a Lazy Student:

• You're solving a complex math problem.
• Every time you find the result of a small sub-problem (e.g., $12 \times 12$), you write it down on a sticky note.
• The next time you see $12 \times 12$, you don't calculate it. You just look at the sticky note.
• You start with the big problem and break it down.

2. Tabulation (Bottom-Up)

Think of Building a House:

• You start with the foundation.
• Then you build the first floor, then the second.
• You build the solution systematically from the smallest pieces until you reach the top.

---

The Fibonacci Example

Calculating Fib(5) requires Fib(4) and Fib(3). Fib(4) also requires Fib(3). Without DP, you calculate Fib(3) twice!

• Recursive (No DP): $O(2^n)$
• With DP: $O(n)$

Comparison

---

javascript Standard
/**
 * Memoization (Top-Down)
 */
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n]; // Check Sticky Note

  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

/**
 * Tabulation (Bottom-Up)
 */
function fibTab(n) {
  if (n <= 1) return n;
  const table = new Array(n + 1).fill(0);
  table[1] = 1;

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}

---

How to identify a DP problem?

1. Min/Max/Total: "Find the minimum cost...", "What is the maximum profit...", "How many ways to...".
2. Repeating Work: If you draw the recursion tree and see the same function calls multiple times.

Top Questions

• Climbing Stairs.
• House Robber.
• Word Break.
• Longest Common Subsequence. 🏯