ReviseAlgo Logo

Dynamic Programming

DP Fundamentals

Master Dynamic Programming foundations: overlapping subproblems, optimal substructure, and Top-down vs Bottom-up methods.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic paradigm that solves a complex problem by breaking it down into simpler subproblems, solving each subproblem exactly once, and storing their solutions to avoid redundant computations.

Why study it?

DP is one of the most frequently tested interview topics. It transforms exponential-time brute-force searches (e.g., O(2^N)) into highly efficient polynomial-time algorithms (e.g., O(N) or O(N²)), separating high-performing candidates.

Where is it Used?

  • Diff Calculators: Git compares lines of code using longest common subsequence algorithms.
  • DNA Sequence Analysis: Finding overlaps in genetic sequence strands using edit distance scoring.

    • 2. Mental Model: Caching Memory

    Imagine a teacher writes on a blackboard:

  • 1 + 1 + 1 + 1 + 1 = ?
  • You count them up and answer: "5".
  • The teacher then writes another + 1 at the end: 1 + 1 + 1 + 1 + 1 + 1 = ?
  • How do you know the answer is "6"?
  • You didn't re-count the first five 1s. You remembered (cached) the previous sum "5", and simply added 1 to it. That is memoization!

    • 3. Core Properties & Approaches

    To apply Dynamic Programming, a problem must satisfy two mathematical conditions: 1. Overlapping Subproblems: The recursive search solves the same subproblem multiple times (e.g., calculating Fib(3) repeatedly while finding Fib(5)). 2. Optimal Substructure: The optimal solution to the problem is composed of optimal solutions to its subproblems.

    Top-Down (Memoization) vs. Bottom-Up (Tabulation)

  • Top-Down (Recursion + Cache):
    • - Starts with the main problem and breaks it down recursively. - Before solving a subproblem, check the cache table. If solved, return immediately; else compute and store. - Pros: Easy to write; only computes subproblems that are actually reached (lazy evaluation). - Cons: Recursion stack overhead can cause stack overflow for large inputs.
  • Bottom-Up (Iteration + Table):
    • - Solves the smallest subproblems first and builds up to the target. - Fills a table iteratively. - Pros: No recursion stack overhead; space-optimization is often possible by discarding older state rows. - Cons: Must evaluate all states in the table (e.g. eager evaluation).

    4. Visualizing Subproblem Pruning

    Brute-force Recursion Tree vs. Memoized Search Path for Fib(5):

    5. Real-World Examples

  • Router Packet Compression: Re-assembling network fragments using sequence alignment caches.
  • Search Spell Checkers: Calculating word differences using cached Edit Distance checks.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test progression:
  • "Given a recurrence relation, optimize it." -> Show the recursive approach first, explain overlapping calculations, implement top-down memoization, convert it to bottom-up tabulation, and optimize the table space from O(N) to O(1) if possible.
  • "Why use Tabulation over Memoization?" -> Explain that Tabulation avoids recursion stack frame allocations, preventing potential Stack Overflow exceptions on deep constraints.

    • Common Mistakes

    Warning: 1. Forgetting to pass/read cache: Declaring a memoization table but failing to return cached entries (if (memo[n] != -1) return memo[n]), leading to a brute-force recursive runtime.
    > 2. Wrong Table Sizing: Declaring a tabulation array of size N instead of N + 1 for problems requiring indices 0 to N (like Fibonacci), resulting in index out of bounds errors.

    7. Summary

  • Memoization (Top-down): Recursion + Cache. Easy, lazy evaluation, stack overhead.
  • Tabulation (Bottom-up): Iterative loop + Table. Stack-safe, eager evaluation, space-optimizable.
  • Conditions: Overlapping Subproblems + Optimal Substructure.

    • 8. Quiz

    Question 1: What is the time complexity of brute-force recursive Fibonacci calculation? Answer: O(2^N) time, due to the tree branching out to double recursion calls at each step.
    Question 2: What is the benefit of Space Optimization in tabulation? Answer: If state transitions only depend on the last few states (like dp[i] = dp[i-1] + dp[i-2]), we only need to store those variables (e.g. prev1 and prev2), reducing auxiliary space complexity from O(N) to O(1).
    Question 3: Does Divide and Conquer (e.g. MergeSort) use Dynamic Programming? Answer: No. Divide and conquer splits problems into non-overlapping subproblems (subarrays are completely separate), whereas DP is specifically used when subproblems overlap.
    Question 4: True or False: Dynamic Programming is always applicable to any problem that can be solved recursively. Answer: False. DP is only useful if subproblems overlap. If there are no overlapping subproblems (e.g., generating all permutations), DP provides no benefits over standard recursion.
    Question 5: What is the space complexity of Top-Down Memoization? Answer: O(N) space, required for both the memoization cache table and the recursive call stack.