Dynamic Programming

Dynamic programming is the paradigm that separates good engineers from great ones. It handles problems that recursion alone cannot solve efficiently — problems where the same subcomputations appear again and again. By storing results instead of recomputing them, DP transforms exponential time into polynomial time.

The name “dynamic programming” was coined by Richard Bellman in the 1950s, and it has nothing to do with “dynamic” in the programming-language sense. Think of it as a systematic way to solve optimization problems by breaking them into overlapping subproblems.

The Two Properties

A problem is a candidate for DP when it exhibits both of these properties:

1. Optimal Substructure

The optimal solution to the problem contains optimal solutions to its subproblems. In other words, you can build the best answer from the best answers to smaller versions of the same question.

Example: the shortest path from A to C through B contains the shortest path from A to B and the shortest path from B to C. If either sub-path were suboptimal, you could replace it with a shorter one and improve the overall path.

2. Overlapping Subproblems

The same subproblems are solved multiple times when using a naïve recursive approach. This is what distinguishes DP from divide and conquer — in D&C, subproblems are independent and never repeat.

Example: computing Fibonacci(50) recursively without memoization calls Fibonacci(48) twice, Fibonacci(47) three times, and Fibonacci(2) over a billion times. The recursion tree explodes because identical subproblems fan out at every level.

Decision rule:

• Optimal substructure + overlapping subproblems → Dynamic Programming
• Optimal substructure + independent subproblems → Divide and Conquer or Greedy
• Neither → look for a different approach

Two Approaches

Top-Down: Memoization

Start from the original problem, recurse into subproblems, and cache each result. When a subproblem recurs, return the cached value instead of recomputing it.

This is the natural extension of brute-force recursion — you add a cache and nothing else changes.

int fibMemo(int n) {
    var cache = new HashMap<Integer, Integer>();
    return fibHelper(n, cache);
}

int fibHelper(int n, Map<Integer, Integer> cache) {
    if (n <= 1) return n;
    if (cache.containsKey(n)) return cache.get(n);

    int result = fibHelper(n - 1, cache) + fibHelper(n - 2, cache);
    cache.put(n, result);
    return result;
}

Advantages: natural to write, computes only the subproblems that are actually needed (lazy evaluation), and handles complex state spaces well.

Bottom-Up: Tabulation

Build a table from the base cases upward, filling in each cell based on previously computed cells. No recursion, no stack overhead.

int fibTab(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Advantages: no recursion overhead, straightforward iteration, easier to apply space optimization (since you can see which cells are still needed).

Which to choose? In interviews, top-down is faster to code because it maps directly from the recursive solution. Bottom-up is preferred when you need space optimization or when the recursion depth would cause stack overflow. Know both.

The DP Recipe

When you face a DP problem, follow these five steps:

Step 1 — Define the state. What does dp[i] (or dp[i][j]) represent? This is the hardest step. The state must capture enough information to make decisions but be compact enough to keep the table size manageable.

Step 2 — Find the recurrence. How does dp[i] relate to previous states? Write the transition formula. This is usually derivable from the problem’s choices: at each step, enumerate your options and take the best one.

Step 3 — Identify base cases. What are the trivial subproblems you can solve directly? These anchor your table and stop the recursion.

Step 4 — Determine computation order. When filling the table bottom-up, ensure that every cell you reference has already been computed. This usually means left-to-right, top-to-bottom, but not always.

Step 5 — Extract the answer. Which cell holds the final result? It is often dp[n] or dp[n-1], but for some problems it is the maximum across a row, or a specific corner of a 2D table.

The Five DP Patterns

Pattern 1: 1D DP

The state depends on a single index. These are the most common interview DP problems.

Climbing Stairs: you can climb 1 or 2 steps at a time. How many distinct ways to reach the top of an $n$-step staircase?

• State: dp[i] = number of ways to reach step i
• Recurrence: dp[i] = dp[i-1] + dp[i-2] (arrive from one step below or two steps below)
• Base cases: dp[0] = 1, dp[1] = 1

House Robber: given an array of house values, maximize stolen value without robbing two adjacent houses.

int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int prev2 = 0;       // dp[i-2]
    int prev1 = nums[0]; // dp[i-1]

    for (int i = 1; i < nums.length; i++) {
        int current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

• State: dp[i] = max value robbing houses 0..i
• Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — skip house i or rob it
• Space optimization: only two previous values are needed → $O(1)$ space instead of $O(n)$

Pattern 2: 2D DP

The state depends on two indices, typically representing positions in a grid or endpoints of a range.

Unique Paths: count paths from top-left to bottom-right of an $m \times n$ grid, moving only right or down.

int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1); // first row: all 1s

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1]; // above + left
        }
    }
    return dp[n - 1];
}

• Full 2D recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]
• Space optimization: since each row depends only on the previous row and the current row’s left neighbor, a single 1D array suffices → $O(n)$ space

Pattern 3: Knapsack DP

You have items with weights and values, and a capacity constraint. Maximize value without exceeding capacity.

0/1 Knapsack (each item used at most once):

int knapsack01(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w]; // skip item i
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

• State: dp[i][w] = max value using items 1..i with capacity w
• Recurrence: skip item i (dp[i-1][w]) or take it (dp[i-1][w-weight[i]] + value[i])
• Note the dp[i-1] in both cases — each item is used at most once

Unbounded Knapsack (items can be reused):

• Recurrence: dp[i][w] = max(dp[i-1][w], dp[i][w-weight[i]] + value[i])
• The change: dp[i] instead of dp[i-1] in the “take” case, allowing item i to be picked again

Coin Change (unbounded knapsack variant): find the minimum number of coins to make a target amount.

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // sentinel "infinity"
    dp[0] = 0;

    for (int coin : coins) {
        for (int a = coin; a <= amount; a++) {
            dp[a] = Math.min(dp[a], dp[a - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Pattern 4: String DP

Two strings, two indices — states represent prefixes of each string.

Longest Common Subsequence (LCS):

int longestCommonSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

• State: dp[i][j] = LCS length of s[0..i-1] and t[0..j-1]
• Recurrence: characters match → extend the diagonal; otherwise → take the better of dropping one character from either string

Edit Distance (Levenshtein Distance): minimum insertions, deletions, and substitutions to transform s into t.

int editDistance(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all
    for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1]; // no cost
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // substitute
                               Math.min(dp[i - 1][j],      // delete
                                        dp[i][j - 1]));     // insert
            }
        }
    }
    return dp[m][n];
}

Pattern 5: Interval DP

The state represents a contiguous range [i, j], and the recurrence tries every possible split point within that range.

Matrix Chain Multiplication: given matrices $A_1, A_2, \ldots, A_n$ with dimensions such that $A_i$ is $p_{i-1} \times p_i$, find the parenthesization that minimizes the total number of scalar multiplications.

int matrixChainOrder(int[] dims) {
    int n = dims.length - 1; // number of matrices
    int[][] dp = new int[n][n];

    // length of chain
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j]
                         + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

• State: dp[i][j] = minimum cost to multiply matrices i through j
• Recurrence: try every split point k between i and j, computing the cost of multiplying the two resulting chains and then combining them
• Computation order: fill by increasing chain length so that smaller intervals are computed first
• Time complexity: $O(n^3)$. Space: $O(n^2)$.

Burst Balloons: given an array of balloons with values, burst all to maximize total coins collected. Bursting balloon k between i and j yields nums[i] * nums[k] * nums[j] coins.

int maxCoins(int[] nums) {
    int n = nums.length;
    int[] vals = new int[n + 2];
    vals[0] = vals[n + 1] = 1;
    System.arraycopy(nums, 0, vals, 1, n);

    int[][] dp = new int[n + 2][n + 2];

    for (int len = 1; len <= n; len++) {
        for (int left = 1; left <= n - len + 1; left++) {
            int right = left + len - 1;
            for (int k = left; k <= right; k++) {
                int coins = vals[left - 1] * vals[k] * vals[right + 1]
                          + dp[left][k - 1] + dp[k + 1][right];
                dp[left][right] = Math.max(dp[left][right], coins);
            }
        }
    }
    return dp[1][n];
}

Space Optimization Techniques

Many DP solutions use $O(n^2)$ space for a 2D table, but the recurrence often references only the previous row. You can exploit this:

Rolling array: keep two rows (current and previous) instead of the full table → $O(n)$ space.

// LCS with rolling array
int lcsOptimized(String s, String t) {
    int m = s.length(), n = t.length();
    int[] prev = new int[n + 1];
    int[] curr = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
        }
        int[] temp = prev;
        prev = curr;
        curr = temp;
        Arrays.fill(curr, 0);
    }
    return prev[n];
}

Single variable: when only two previous values are needed (like Fibonacci or House Robber), collapse the entire array to $O(1)$ space.

Common DP States

Recognizing the state is the hardest part. Here are common state dimensions:

State	Example	Meaning
Index i	House Robber	Position in the array
Index i, j	LCS, Edit Distance	Positions in two strings
Index i, capacity w	Knapsack	Item index + remaining capacity
Interval [i, j]	Matrix Chain	Range of elements
Bitmask mask	TSP	Subset of visited elements

Bitmask DP

When the state includes a subset of elements (and $n \leq 20$), represent the subset as a bitmask. The state space becomes $2^n$ subsets.

Traveling Salesman Problem (TSP): find the shortest cycle visiting all $n$ cities exactly once.

int tsp(int[][] dist, int n) {
    int fullMask = (1 << n) - 1;
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    dp[1][0] = 0; // start at city 0

    for (int mask = 1; mask <= fullMask; mask++) {
        for (int u = 0; u < n; u++) {
            if ((mask & (1 << u)) == 0) continue;
            if (dp[mask][u] == Integer.MAX_VALUE / 2) continue;

            for (int v = 0; v < n; v++) {
                if ((mask & (1 << v)) != 0) continue;
                int nextMask = mask | (1 << v);
                dp[nextMask][v] = Math.min(dp[nextMask][v],
                                           dp[mask][u] + dist[u][v]);
            }
        }
    }

    int result = Integer.MAX_VALUE;
    for (int u = 1; u < n; u++) {
        result = Math.min(result, dp[fullMask][u] + dist[u][0]);
    }
    return result;
}

• State: dp[mask][i] = minimum cost to visit the cities in mask, ending at city i
• Time: $O(2^n \cdot n^2)$, feasible for $n \leq 20$
• Space: $O(2^n \cdot n)$

Bitmask DP is a niche technique, but it appears in competitive programming and advanced interviews. The key indicator: “visit all elements” or “assign all tasks” with $n$ small enough for exponential states.

Interviewer Tips

1. Recognize DP problems by their keywords: “minimum cost,” “maximum profit,” “number of ways,” “can you reach…?” and “longest/shortest” all suggest DP.
2. Start top-down. Write the brute-force recursive solution first, then add memoization. This is the fastest path to a correct solution under interview pressure.
3. Convert to bottom-up if asked. Once the top-down solution works, the bottom-up version follows mechanically: replace recursion with loops, memoization with a table.
4. State your state clearly. Say “dp[i] represents the maximum value considering items 0 through i” out loud. If you can’t articulate the state, you don’t have a solution yet.
5. Optimize space last. Get the correct solution first with full tables, then reduce to rolling arrays or single variables. Premature space optimization introduces bugs.
6. Practice the five patterns. Every DP interview problem fits one of the five patterns above. Drill two or three problems per pattern until the state design becomes instinctive.