Dynamic Programming Guide: From Memoization to Tabulation

Algorithms Algorithms 8 min read 1603 words Beginner ExcellentWiki Editorial Team

Dynamic programming (DP) is a method for solving complex problems by breaking them down into simpler overlapping subproblems. It is one of the most powerful techniques in algorithm design, turning exponential-time brute force solutions into polynomial-time algorithms. The core insight is simple: if a problem has optimal substructure and overlapping subproblems, you can store intermediate results to avoid recomputation.

Core Concepts

Optimal Substructure

A problem has optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. Shortest path problems have optimal substructure — the shortest path from A to C via B includes the shortest path from A to B. Greedy algorithms also exploit optimal substructure, but DP handles cases where greedy fails. For example, the knapsack problem has optimal substructure but no greedy solution works because taking a locally optimal item might force you to miss a better combination later.

Overlapping Subproblems

Overlapping subproblems occur when the same subproblem is solved multiple times. The Fibonacci sequence is the canonical example: computing fib(5) requires fib(4) and fib(3), but fib(4) itself requires fib(3) and fib(2). Without DP, fib(3) is computed twice — the waste grows exponentially with n. The naive recursive Fibonacci has O(2^n) time complexity, while the DP version achieves O(n).

Approaches to Dynamic Programming

Top-Down (Memoization)

Start with the original problem and recursively break it down, caching results as you go.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Advantages: Intuitive, only solves needed subproblems, easy to derive from recursive solution.

Disadvantages: Recursion overhead, potential stack overflow for deep recursion.

Bottom-Up (Tabulation)

Solve subproblems in order of increasing size, building up to the original problem.

def fib_tab(n):
    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]

Advantages: No recursion overhead, often better cache performance, easier to optimize space.

Disadvantages: Solves all subproblems even if not needed, can be less intuitive.

Classic DP Problems

0/1 Knapsack

Given items with weights and values, maximize value without exceeding capacity. Each item can be taken at most once.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i - 1][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

Complexity: O(n × capacity) time, O(n × capacity) space (can be optimized to O(capacity)).

Longest Common Subsequence (LCS)

Find the longest subsequence common to two strings.

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Applications: Diff tools, DNA sequence alignment, plagiarism detection.

Longest Increasing Subsequence (LIS)

Find the longest subsequence where elements are in strictly increasing order.

def lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Optimization: Use patience sorting for O(n log n) solution.

Edit Distance (Levenshtein Distance)

Minimum number of operations (insert, delete, replace) to transform one string into another. The recurrence is: if characters match, carry forward the diagonal value; otherwise take 1 plus the minimum of insert, delete, or replace. Edit distance is used in spell checkers, DNA sequence alignment, and natural language processing. The time complexity is O(m × n) and space can be reduced to O(min(m, n)).

Coin Change (Unbounded Knapsack)

Given coin denominations and a target amount, find the minimum number of coins needed. Unlike 0/1 knapsack, each coin can be used unlimited times. The DP state dp[i] represents the minimum coins needed for amount i. The recurrence dp[i] = min(dp[i], dp[i - coin] + 1) is computed for each coin and each amount. This unbounded pattern generalizes to other problems where items have infinite copies.

Pattern Recognition

Most DP problems fall into recognizable patterns:

Fibonacci-style: One-dimensional DP where state depends on previous states. Examples: climbing stairs, house robber, decoding ways.
Grid-based: Two-dimensional DP for paths in a matrix. Examples: unique paths, minimum path sum, maximal square.
Sequence matching: Two-dimensional DP comparing sequences. Examples: LCS, edit distance, wildcard matching.
Partition: Dividing input into optimal segments. Examples: palindrome partitioning, word break, burst balloons.
Interval DP: Solving problems on subarrays. Examples: matrix chain multiplication, optimal BST, stone game.
Tree DP: DP on tree structures. Examples: tree diameter, maximum path sum, house robber III.
Bitmask DP: Using bitmasks to represent state subsets. Examples: traveling salesman, assignment problem, Hamiltonian path.

Recognizing these patterns is the fastest path to solving DP problems. When you encounter a new problem, first ask: which pattern does this resemble? Does it involve pairs of indices (LCS style), subarrays (interval), or inclusion-exclusion of elements (bitmask)?

Bitmask DP in Detail

Bitmask DP uses an integer bitmask to represent which elements of a set have been used. Each bit corresponds to one element. The state dp[mask][i] stores the optimal value for having visited the set represented by mask and ending at element i. The traveling salesman problem is the classic example: dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i]) for all j in mask. The total number of states is O(2^n × n), limiting this technique to n ≤ 20 in practice.

Space Optimization

Many DP solutions can be optimized to use less memory. When the recurrence only depends on the previous row, you can use rolling arrays.

def knapsack_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

The iteration order matters: iterating capacity backwards ensures each item is used at most once. For the unbounded knapsack (unlimited copies), iterate capacity forwards. This pattern of iterating backwards for 0/1 and forwards for unbounded is a key DP implementation detail that applies to many problems beyond knapsack.

Common Pitfalls

Wrong state definition: The most common mistake. The DP state must capture all information needed for future decisions.
Missing base cases: Always define and test base cases before building the DP table.
Incorrect recurrence: Verify your recurrence on small examples. Trace through by hand.
Off-by-one errors: Be careful with indexing — dp[i] often represents the first i elements, not the i-th element.
Forgetting initialization: The DP table should be initialized correctly (often with 0, infinity, or -1).

When to Use Dynamic Programming

Ask three questions:

Can the problem be divided into smaller subproblems?
Do subproblems overlap (not just partition like divide-and-conquer)?
Does the optimal solution depend on optimal solutions to subproblems?

If all answers are yes, DP is likely the right approach. If the problem is asking for the number of ways to do something, the minimum or maximum of something, or whether something is possible under constraints, DP is a strong candidate. If subproblems are independent rather than overlapping, divide-and-conquer (like mergesort) is the better choice.

Conclusion

Dynamic programming is a skill that develops with practice. Start by recognizing the classic patterns — knapsack, LCS, LIS, edit distance — and understand why the recurrence works. Draw the DP table by hand for small inputs. Gradually move to harder problems that require more complex state definitions. With consistent practice, DP becomes a powerful tool in your algorithmic toolkit.

FAQ

What is the difference between memoization and tabulation? Memoization (top-down) caches results of a recursive function as they are computed, solving only needed subproblems. Tabulation (bottom-up) iteratively fills a table from the smallest subproblems upward, solving all subproblems regardless of whether they are needed. Memoization is easier to derive; tabulation is usually faster.

How do I recognize a DP problem in an interview? Look for keywords like “maximum,” “minimum,” “number of ways,” “longest,” “shortest,” “optimal.” The problem will ask for an optimal value or count rather than the actual solution. Check if decisions at each step affect future possibilities — if yes, greedy may fail and DP may be needed.

Can I always optimize DP space to O(1)? Only when the recurrence depends on a constant number of previous states. Fibonacci depends on only two previous states, so O(1) space works. LCS needs a full 2D table if you need to reconstruct the subsequence, but can be reduced to O(min(m, n)) for just the length.

What is the hardest part of DP? Defining the state correctly. The state must capture everything the algorithm needs to make future decisions without remembering the entire history. A good rule: if your state has more than 2-3 dimensions, look for a simpler formulation or consider whether some dimensions can be derived from others.

How do I reconstruct the actual solution (not just the optimal value)? Maintain a separate 2D table or parallel array that records the decision made at each state. For knapsack, store whether each item was taken. For LCS, store arrows indicating the direction of the optimal choice. Backtrack through this decision table after computing the DP table to reconstruct the solution.