Dynamic Programming: From Basics to Advanced

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems and reusing solutions. It turns exponential-time problems into polynomial-time.

When to Use DP

A problem is solvable with DP if it has:

1. Optimal substructure: Optimal solution can be built from optimal solutions of subproblems
2. Overlapping subproblems: Same subproblems are solved multiple times

Examples

Two Approaches

Top-Down (Memoization)

Recursive with caching:

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

Pros: Only solves needed subproblems, intuitive Cons: Recursion overhead, possible stack overflow

Bottom-Up (Tabulation)

Iterative, building from smallest subproblems:

def fib(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]

Space-optimized:

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Pros: No recursion overhead, often faster Cons: May compute unnecessary subproblems

Classic DP Problems

1. Climbing Stairs

Ways to climb n stairs, taking 1 or 2 steps at a time.

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Same as Fibonacci with different base cases.

2. 0/1 Knapsack

Max value with weight limit W, each item taken at most once.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

Time: O(nW) Space: O(nW), can optimize to O(W)

3. Longest Common Subsequence (LCS)

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]

4. Longest Increasing Subsequence (LIS)

def length_of_lis(nums):
    tails = []
    for num in nums:
        i = 0
        j = len(tails)
        while i < j:
            mid = (i + j) // 2
            if tails[mid] < num:
                i = mid + 1
            else:
                j = mid
        if i == len(tails):
            tails.append(num)
        else:
            tails[i] = num
    return len(tails)

Time: O(n log n)

5. Edit Distance (Levenshtein)

Minimum operations (insert, delete, replace) to convert one string to another.

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

DP Problem-Solving Framework

1. Define state: What does dp[i][j] represent?
2. Find recurrence: How does dp[i][j] relate to smaller subproblems?
3. Base cases: What are the smallest subproblems?
4. Iteration order: Do you go left-to-right, top-to-bottom?
5. Optimize: Can you reduce space?

Common State Patterns

| Pattern | Example State | |

Tabular Approach

# 1. Define dimensions
dp = [[0] * W for _ in range(N)]

# 2. Base cases
dp[0][j] = 0
dp[i][0] = 0

# 3. Fill the table
for i in range(1, N):
    for j in range(1, W):
        # 4. Recurrence
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])

# 5. Extract answer
return dp[N-1][W-1]

Common Mistakes

• Not identifying overlapping subproblems — if subproblems don’t overlap, DP doesn’t help
• Wrong state definition — leads to incorrect recurrence
• Off-by-one errors — double-check indices
• Missing base cases — the foundation of the DP table
• Optimizing too early — get the correct DP first, then optimize

Master DP by practicing the classic problems. The patterns repeat across hundreds of LeetCode problems.

Dynamic Programming Fundamentals

Optimal Substructure and Overlapping Subproblems

Two properties are necessary for applying dynamic programming. Optimal substructure means the optimal solution to the problem contains optimal solutions to subproblems — the shortest path between two nodes includes shortest paths between intermediate nodes. Overlapping subproblems means the same subproblems are solved multiple times — computing the Fibonacci sequence recalculates the same values repeatedly. Identifying these properties determines whether DP is applicable. Classic examples with clear optimal substructure include longest common subsequence, subset sum, shortest path, and minimum edit distance. Problems without these properties, like the traveling salesman with non-overlapping substructures, require alternative approaches such as branch and bound.

Top-Down vs. Bottom-Up DP

Top-down dynamic programming (memoization) starts with the original problem and recursively breaks it into subproblems, caching results as they are computed. The advantage is that only necessary subproblems are solved — if the full subproblem space is not needed, memoization saves computation. Bottom-up DP (tabulation) starts with the smallest subproblems and iteratively builds up to the original problem. Tabulation avoids recursion overhead and makes space optimization easier — for many problems, only the last few rows of the DP table need to be retained. The choice between approaches depends on the subproblem dependency graph. For grid-based problems like minimum path sum where all subproblems are required, bottom-up is natural. For problems with sparse subproblem dependencies, top-down may be more efficient.

Common DP Patterns

The knapSack pattern (include or exclude each item) appears in resource allocation, portfolio optimization, and combinatorial selection. The longest common subsequence pattern extends to sequence alignment, diff algorithms, and DNA matching. The matrix chain multiplication pattern (optimal parenthesization) applies to parsing and expression evaluation. The DP on intervals pattern handles problems where solutions combine left and right subintervals — optimal BST construction, palindrome partitioning. The DP on digits pattern counts numbers satisfying digit-level constraints. Recognizing these patterns helps map new problems to existing solution templates. Each pattern has characteristic state definitions, transition formulas, and initialization procedures.

Optimization Techniques

Space Optimization

Many DP solutions can be optimized from O(n²) to O(n) space by observing that only the previous row (or a few previous rows) is needed for computation. The longest common subsequence problem typically uses a 2D table of size (m+1) × (n+1), but only the current and previous rows are required for computation, reducing space to O(min(m, n)). The knapSack problem’s 2D DP table can be compressed to a 1D array when iterating capacity in reverse order — because each item can be used at most once, processing from high to low capacity ensures each item is not reused. The edit distance problem similarly uses only two rows of the DP table. These optimizations require careful ordering of loops to ensure that previously computed values are available when needed and not overwritten prematurely.

State Compression and Bitmask DP

When the state space is large but each dimension has a small number of values, bitmask DP (also called DP with bitmask or DP over subsets) represents subsets as integer bitmasks. The traveling salesman problem with n cities requires DP over subsets — dp[mask][v] represents the minimum cost to visit cities in mask and end at city v. With n ≤ 20, this is tractable with O(2ⁿ × n²) time. Bipartite matching, Hamiltonian path, and set cover problems all use bitmask DP. The state representation uses bit operations extensively: mask | (1 « u) to add element u, mask & (1 « u) to check membership. The challenge is identifying when bitmask DP is appropriate — the state must represent a subset of elements, and the transition must depend only on the subset and a single current element.

Frequently Asked Questions

What is the difference between memoization and tabulation? Memoization is top-down — it caches results of recursive function calls as they are computed. Tabulation is bottom-up — it fills a table iteratively from base cases to the target. Memoization solves only needed subproblems but has recursion overhead. Tabulation potentially solves all subproblems but avoids recursion and enables space optimization.

How do I identify if a problem can be solved with DP? Look for two properties: optimal substructure (can the optimal solution be built from optimal solutions to subproblems?) and overlapping subproblems (are the same subproblems solved multiple times?). Common signs: asking for the count of ways, the minimum/maximum of something, or whether something is possible given constraints.

What is the time complexity of DP solutions? Time complexity is typically O(number of states × transition cost). The number of states equals the product of state dimension ranges. For the 0/1 knapSack with n items and capacity W, time is O(nW). For longest common subsequence of strings length n and m, time is O(nm). Always analyze the state space before implementing.

Sorting Algorithms Guide — Searching Algorithms Guide — Graph Algorithms Guide