What is dynamic programming (DP)?

AlgorithmsJunior~3 min read

Short answer

Dynamic programming (DP) is a method for solving problems by breaking them into overlapping subproblems, remembering results (memoization) or incrementally building a table of answers (tabulation), using the property of optimal substructure.

Signs: optimal substructure and overlapping subproblems.
Approaches: Top-Down (memoization) and Bottom-Up (tabulation).
Goal: reduce exponential complexity to polynomial.

Detailed breakdown

DP is used when the best solution to a problem can be assembled from the best solutions to its subproblems, and the subproblems themselves repeat. Instead of recomputing them, we store the results and reuse them.

When to use DP

There is optimal substructure: the optimum of the larger problem is built from the optima of smaller ones.
Subproblems overlap: there is a set of repeated computations.
Examples: Fibonacci, 0/1 knapsack, grid paths, coin change, LCS/LIS, string editing (Levenshtein).

Key ideas

State: how to parameterize the subproblem, for example dp[i][w] is the best answer for the first i items and weight w.
Recurrence: how to compute the current state from smaller ones.
Base: the values for the smallest cases.
Computation order: a topological order of dependencies.

Approaches: Top-Down and Bottom-Up

Top-Down (memoization): recursively solve the subproblem and cache the result. Easier to write, mirrors the mathematical definition, but risks stack overflow.
Bottom-Up (tabulation): build the table from the base cases to the answer. You control the order and memory, with no deep recursion.

Solution template

Define the dp state (which parameters are enough to store).
Describe the base cases (initialization).
Derive the recurrence.
Choose the computation order (or use recursion plus memoization).
Determine where the answer lives (dp[n], dp[n][m], the maximum over a row/column, and so on).
Estimate the time and memory complexity.
If needed, plan to store pointers/reconstruct the solution with a backward pass.

Code examples

Fibonacci - memoization (Top-Down)

python

from functools import lru_cache

@lru_cache(None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55

Fibonacci - tabulation (Bottom-Up)

python

def fib(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib(10))  # 55

0/1 Knapsack (maximum value under a weight limit)

State: dp[i][w] is the maximum value using the first i items with allowed weight w.

Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1]) if wt[i-1] <= w, otherwise dp[i][w] = dp[i-1][w].

python

from typing import List

def knapsack(W: int, wt: List[int], val: List[int]) -> int:
    n = len(wt)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if wt[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
    return dp[n][W]

print(knapsack(7, [1, 3, 4, 5], [1, 4, 5, 7]))  # 9

Counting grid paths (memory optimization)

The number of paths from (0,0) to (m-1,n-1) moving right/down. State: dp[j] is the number of paths to the current cell in the row. Recurrence: dp[j] += dp[j-1].

python

def unique_paths(m: int, n: int) -> int:
    dp = [1] * n  # base first row: only moving right
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[-1]

print(unique_paths(3, 7))  # 28

Memory optimization and reconstructing the answer

Memory optimization: reduce dp to 1D, or to two rolling rows/columns, if the transition only uses neighboring layers.
Reconstructing the solution: store pointers (parent/choice), or recompute by walking backward from the answer, checking which transition equality holds.

Common mistakes in DP

The state is defined incorrectly (missing parameters, or too many of them).
Incomplete base cases: incorrect boundary initialization.
Wrong computation order for tabulation.
Stack overflow from deep recursion (better to switch to Bottom-Up).

How to answer in an interview

Give the definition of DP and its two signs: optimal substructure, overlapping subproblems.
Describe Top-Down and Bottom-Up, and when to choose each.
Give a mini example (Fibonacci/knapsack) with the state, recurrence, and complexity estimate.
Mention memory optimization and reconstructing the answer.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.