Dynamic Programming: Memoization vs. Tabulation

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. The Core DP Philosophy

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into overlapping subproblems and caching intermediate solutions so each subproblem is solved exactly once.

2. The Two Necessary Properties for DP

1. Overlapping Subproblems: The same subproblems are solved repeatedly (e.g. Fibonacci: $F(5) = F(4) + F(3)$, where $F(3)$ is computed in both branches).
2. Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions to its subproblems.

3. Top-Down DP (Memoization)

Start with natural recursion and store computed results in a cache:

// Climbing Stairs: You can take 1 or 2 steps. How many ways to reach step N?
function climbStairsMemo(n, memo = new Map()) {
  if (n <= 2) return n;
  if (memo.has(n)) return memo.get(n); // Return cached result!

  const result = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(climbStairsMemo(5)); // Output: 8

4. Bottom-Up DP (Tabulation)

Eliminate recursion entirely by filling an iterative table from base cases upward:

function climbStairsTab(n) {
  if (n <= 2) return n;

  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;

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

  return dp[n];
}

// Space Optimized: O(1) Space!
function climbStairsOptimized(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;

  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

5. Comparison Matrix

6. Common Mistakes

• Applying DP When Subproblems Do Not Overlap: Divide and conquer (e.g. Merge Sort) breaks problems into independent, non-overlapping subproblems. DP only applies when subproblems overlap!

7. Next Steps

Identify state transitions and base cases. Next, let's explore the 0/1 Knapsack Pattern!