Dynamic Programming (Basics)

Dynamic Programming (DP) is arguably the most feared algorithmic paradigm in coding interviews. At its core, DP is just an optimization over plain Recursion.

If a recursive algorithm solves the exact same subproblem multiple times, it wastes massive amounts of CPU cycles. DP solves each subproblem exactly once and saves the answer in memory.

The Two Requirements for DP

1. Overlapping Subproblems: The algorithm asks the exact same question repeatedly.
2. Optimal Substructure: The optimal solution to the main problem can be constructed directly from the optimal solutions of its subproblems.

The Classic Example: Fibonacci

$Fib(N) = Fib(N-1) + Fib(N-2)$

1. Naive Recursion (The Problem)

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

Notice how fib(3) is calculated twice! fib(2) is calculated three times! Because of this redundancy, the Time Complexity is an abysmal $O(2^N)$. Calling fib(50) will literally freeze your computer for hours.

Approach 1: Top-Down (Memoization)

We keep the recursion, but we pass a "Memo" (a Cache/Hash Map). Before doing any math, we check if the answer is in the cache. If it is, we return it instantly.

function fibMemo(n: number, cache: Map<number, number> = new Map()): number {
  if (n <= 1) return n;
  
  // Did we already calculate this?
  if (cache.has(n)) {
    return cache.get(n)!;
  }
  
  // No? Calculate it and SAVE it.
  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result);
  
  return result;
}

Time Complexity drops from $O(2^N)$ to $O(N)$! We only calculate each number once.

Approach 2: Bottom-Up (Tabulation)

We ditch recursion entirely. Instead of starting at the top fib(50) and working down to the base cases, we start at the base cases fib(0) and build an array (a Table) all the way up to fib(50).

function fibTab(n: number): number {
  if (n <= 1) return n;
  
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = 1;
  
  for (let i = 2; i <= n; i++) {
    // The current answer is built from the two previous answers in the table!
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

Time Complexity: $O(N)$ Space Complexity: $O(N)$ (Can be heavily optimized to $O(1)$ by only keeping track of the last two variables instead of a massive array).

Memoization vs Tabulation