Dynamic Programming Fundamentals

Dynamic Programming (DP) is just a fancy name for remembering answers to subproblems so we don’t solve them again. That’s it. If we’ve already computed something, we save it and reuse it next time.

In simple language, it’s like writing answers on a cheat sheet as we go. Instead of recalculating the same thing 50 times, we look it up from our notes.

The Two Key Properties

A problem is a good candidate for DP when it has both of these:

1. Overlapping Subproblems — the same smaller problems come up again and again. If every subproblem is unique, DP won’t help us.
2. Optimal Substructure — the best solution to the big problem can be built from best solutions to its subproblems.

Fibonacci: The Hello World of DP

Let’s start with the classic. The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13…

Each number is the sum of the two before it: fib(n) = fib(n-1) + fib(n-2).

The Naive Way (Exponential — Terrible)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // same calls happen over and over
}
// fib(5) triggers 15 function calls!

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # same calls happen over and over
# fib(5) triggers 15 function calls!

static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // same calls happen over and over
}
// fib(5) triggers 15 function calls!

Here’s the problem — look at how many times the same values get computed:

This is O(2ⁿ) time. For fib(50), that’s over a trillion calls. Yikes.

Approach 1: Memoization (Top-Down)

We start from the top (the original problem) and recurse down, but we cache results in a hash map. Before computing anything, we check if we already know the answer.

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n];     // already solved? return it
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
// fib(50) now runs instantly — O(n) time, O(n) space

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]              # already solved? return it
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]
# fib(50) now runs instantly — O(n) time, O(n) space

static Map<Integer, Integer> memo = new HashMap<>();
static int fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n); // already solved?
    memo.put(n, fib(n - 1) + fib(n - 2));
    return memo.get(n);
}
// fib(50) now runs instantly — O(n) time, O(n) space

Approach 2: Tabulation (Bottom-Up)

We start from the smallest subproblems and build up to the answer using an array (the “table”). No recursion at all.

function fib(n) {
  if (n <= 1) return n;
  const dp = [0, 1];                // base cases
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // build from bottom up
  }
  return dp[n];
}

def fib(n):
    if n <= 1:
        return n
    dp = [0, 1]                      # base cases
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build from bottom up
    return dp[n]

static int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;             // base cases
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // build from bottom up
    }
    return dp[n];
}

Space-Optimized (Constant Space)

We only ever need the last two values. No need for a whole array.

function fib(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;   // only keep what we need
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1; // O(1) space!
}

def fib(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2     # only keep what we need
        prev2 = prev1
        prev1 = curr
    return prev1  # O(1) space!

static int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2; // only keep what we need
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1; // O(1) space!
}

Memoization vs Tabulation

Pro tip: In interviews, start with memoization (it’s easier to think about). Then optimize to tabulation if the interviewer asks.

How to Recognize DP Problems

Look for these signals:

1. “Find the minimum/maximum…” — optimization problems love DP.
2. “How many ways to…” — counting problems are classic DP.
3. “Can we reach / is it possible…” — feasibility checks with choices.
4. The choices at each step affect future choices — greedy won’t work, we need to explore combinations.
5. The problem has a recursive structure — and we see the same subproblems repeating.

Common keywords: minimum cost, maximum profit, number of ways, longest/shortest, can we partition, is it possible.

The DP Recipe

Here’s a step-by-step process that works for most DP problems:

1. Define the state — what does dp[i] (or dp[i][j]) represent?
2. Find the recurrence — how does dp[i] relate to smaller subproblems?
3. Identify base cases — what are the trivial answers we know right away?
4. Determine computation order — which direction do we fill the table?
5. Optimize space — can we drop dimensions we no longer need?

This recipe will carry us through 90% of DP problems in interviews. Let’s apply it across the next few notes.