CS Glossary

Dynamic Programming (DP)

An optimization technique that solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant computation.

Time: Depends on the number of states × time per state (usually O(n) to O(n²) for interview problems) Space: O(n) for 1D DP, O(n²) for 2D DP; often optimizable to O(1) or O(n)

Overview

Dynamic Programming (DP) is the most feared interview topic — and the most rewarding to master. DP solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results. The two key properties are: (1) optimal substructure — the optimal solution contains optimal solutions to subproblems, and (2) overlapping subproblems — the same subproblems are solved multiple times. DP can be implemented top-down (recursion + memoization) or bottom-up (tabulation).

How It Works

1 Identify the state: what parameters uniquely define a subproblem? (e.g., dp[i] = answer for first i elements)
2 Define the recurrence: how does dp[i] relate to smaller subproblems? (e.g., dp[i] = dp[i-1] + dp[i-2])
3 Set base cases: what are the trivial subproblems? (e.g., dp[0] = 0, dp[1] = 1)
4 Determine the computation order: which subproblems must be solved first? (bottom-up: left to right; top-down: recursion handles it)
5 Optionally optimize space: if dp[i] only depends on dp[i-1] and dp[i-2], you only need two variables, not an array.

Complexity Analysis

Time: Depends on the number of states × time per state (usually O(n) to O(n²) for interview problems) Space: O(n) for 1D DP, O(n²) for 2D DP; often optimizable to O(1) or O(n)

The time complexity equals the number of unique subproblems multiplied by the work done per subproblem. For 1D DP with n states, it is typically O(n) or O(n²). Space can often be optimized by observing that only a few previous states are needed.

When to Use

→Counting problems: "how many ways to reach the end"
→Optimization problems: "minimum cost", "maximum profit", "longest subsequence"
→String problems: edit distance, longest common subsequence, word break
→Knapsack variants: 0/1 knapsack, unbounded knapsack, subset sum
→Interval problems: burst balloons, palindrome partitioning
→Grid problems: unique paths, minimum path sum

Common Mistakes

⚠Not identifying the correct state definition — if dp[i] does not capture all needed information, the recurrence is wrong
⚠Forgetting base cases or setting them incorrectly
⚠Wrong computation order in bottom-up DP (dependencies not yet computed)
⚠Not recognizing that the problem has overlapping subproblems (pure recursion works but is exponential)
⚠Trying to optimize space before getting the correct O(n) solution first

Code Examples

// Fibonacci — bottom-up tabulation
int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// Fibonacci — bottom-up tabulation
int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

# Fibonacci — top-down with memoization
from functools import lru_cache

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

# Bottom-up tabulation
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]

// Fibonacci — bottom-up tabulation
function fib(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

Related Patterns

◫ Dynamic Programming

Practice Problems

Climbing Stairs	Easy
Coin Change	Medium
Longest Increasing Subsequence	Medium
Word Break	Medium
Edit Distance	Hard

Frequently Asked Questions

What is dynamic programming and when should I use it?

Dynamic programming (DP) is an optimization technique for problems with two properties: (1) optimal substructure — the optimal solution contains optimal solutions to subproblems, and (2) overlapping subproblems — the same subproblems are solved repeatedly. Use DP when: counting ways, finding minimum/maximum, or when brute force has exponential time but the problem has these two properties.

What is the difference between top-down and bottom-up DP?

Top-down DP uses recursion with memoization — you write the natural recursive solution and cache results. Bottom-up DP uses tabulation — you fill a table iteratively from base cases to the final answer. Top-down is easier to write (follows the natural recursion); bottom-up is often faster (no recursion overhead) and uses less memory when space-optimized.

How do I identify if a problem can be solved with DP?

Look for these signals: (1) The problem asks for "count the number of ways", "minimum cost", "maximum profit", or "longest subsequence". (2) The brute force solution has overlapping subproblems (same state computed multiple times). (3) Making a choice at each step leads to a smaller subproblem. (4) The problem can be broken into independent subproblems whose solutions combine.

Master this concept with practice

Browse all patterns and problems to build systematic interview intuition.

All Patterns Roadmap