Dynamic Programming | Computer Science Fundamentals

Introduction

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems, solving each once, and storing the results. It's one of the most powerful algorithmic techniques and essential for coding interviews.

Learning Objectives

By the end of this reading, you will be able to:

Identify when to use dynamic programming
Apply top-down (memoization) and bottom-up (tabulation) approaches
Solve classic DP problems
Optimize space in DP solutions

1. When to Use DP

DP applies when a problem has:

Optimal Substructure: Optimal solution contains optimal solutions to subproblems
Overlapping Subproblems: Same subproblems are solved multiple times

Example: Fibonacci

# Without DP - O(2^n) time
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# Visualize the problem:
# fib(5)
# ├── fib(4)
# │   ├── fib(3)
# │   │   ├── fib(2)
# │   │   └── fib(1)
# │   └── fib(2)      ← REPEATED
# └── fib(3)          ← REPEATED
#     ├── fib(2)      ← REPEATED
#     └── fib(1)

2. Two Approaches

Top-Down (Memoization)

Start with the original problem, recursively solve subproblems, cache results.

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}

    if n in cache:
        return cache[n]

    if n <= 1:
        return n

    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    return cache[n]

# Using decorator
from functools import lru_cache

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

Bottom-Up (Tabulation)

Solve subproblems first, build up to original problem.

def fib_tabulation(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 - O(1) space
def fib_optimized(n):
    if n <= 1:
        return n

    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

Comparison

Aspect	Top-Down	Bottom-Up
Implementation	Often easier	May need to think about order
Overhead	Recursion overhead	None
Subproblems	Only computes needed	Computes all
Space optimization	Harder	Easier

3. DP Problem-Solving Framework

Step 1: Define State

What information do we need to represent a subproblem?

Example: "What's the minimum cost to reach step i?"

Step 2: Define Recurrence

How does the solution to a subproblem relate to smaller subproblems?

Example: dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

Step 3: Identify Base Cases

What are the smallest subproblems we can solve directly?

Example: dp[0] = cost[0], dp[1] = cost[1]

Step 4: Determine Order

For bottom-up: In what order should we solve subproblems?

Step 5: Optimize (Optional)

Can we reduce space complexity?

4. Classic DP Problems

Climbing Stairs

"""
You can climb 1 or 2 steps at a time. How many ways to reach step n?

State: dp[i] = number of ways to reach step i
Recurrence: dp[i] = dp[i-1] + dp[i-2]
Base: dp[0] = 1, dp[1] = 1
"""

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

# Space optimized
def climb_stairs_opt(n):
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

Coin Change (Minimum Coins)

"""
Given coins and amount, find minimum coins needed.

State: dp[i] = minimum coins to make amount i
Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin
Base: dp[0] = 0
"""

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Coin Change (Number of Ways)

"""
Count the number of ways to make amount.

State: dp[i] = number of ways to make amount i
Recurrence: dp[i] += dp[i - coin] for each coin
Base: dp[0] = 1
"""

def coin_change_ways(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:  # Process each coin
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

Longest Increasing Subsequence (LIS)

"""
Find length of longest strictly increasing subsequence.

State: dp[i] = length of LIS ending at index i
Recurrence: dp[i] = max(dp[j] + 1) for j < i where arr[j] < arr[i]
Base: dp[i] = 1 (each element is a subsequence)
"""

def longest_increasing_subsequence(arr):
    if not arr:
        return 0

    n = len(arr)
    dp = [1] * n  # Each element is LIS of length 1

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# O(n log n) solution using binary search
import bisect

def lis_optimized(arr):
    sub = []  # Smallest tail of all increasing subsequences

    for num in arr:
        pos = bisect.bisect_left(sub, num)
        if pos == len(sub):
            sub.append(num)
        else:
            sub[pos] = num

    return len(sub)

Longest Common Subsequence (LCS)

"""
Find length of longest common subsequence of two strings.

State: dp[i][j] = LCS of s1[0:i] and s2[0:j]
Recurrence:
  If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
  Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Base: dp[0][j] = dp[i][0] = 0
"""

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[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]

# Space optimized to O(n)
def lcs_optimized(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)

    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev = curr

    return prev[n]

Edit Distance

"""
Minimum operations (insert, delete, replace) to transform s1 to s2.

State: dp[i][j] = edit distance between s1[0:i] and s2[0:j]
Recurrence:
  If s1[i-1] == s2[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])
Base: dp[0][j] = j, dp[i][0] = i
"""

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    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 s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete
                    dp[i][j-1],    # Insert
                    dp[i-1][j-1]   # Replace
                )

    return dp[m][n]

0/1 Knapsack

"""
Given weights, values, and capacity. Maximize value without exceeding capacity.
Each item can be taken at most once.

State: dp[i][w] = max value using items 0..i-1 with capacity w
Recurrence:
  dp[i][w] = max(dp[i-1][w],                      # Don't take item i
                 dp[i-1][w-weight[i]] + value[i]) # Take item i
Base: dp[0][w] = 0
"""

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):
            # Don't take item i-1
            dp[i][w] = dp[i-1][w]
            # Take item i-1 if possible
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                              dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

# Space optimized to O(capacity)
def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        # Traverse backward to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

5. DP Patterns

Linear DP

Single array, each state depends on previous states.

# House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = 0, 0
    for num in nums:
        current = max(prev1, prev2 + num)
        prev2, prev1 = prev1, current

    return prev1

2D DP

Grid or two sequences.

# Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

Interval DP

Subproblem defined by interval [i, j].

# Matrix Chain Multiplication
def matrix_chain(dims):
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):  # Length of chain
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n-1]

State Machine DP

States represent different conditions.

# Best Time to Buy/Sell Stock with Cooldown
def max_profit_cooldown(prices):
    if not prices:
        return 0

    n = len(prices)
    hold = -prices[0]  # Holding stock
    sold = 0           # Just sold
    rest = 0           # Not holding, not sold

    for i in range(1, n):
        prev_hold = hold
        prev_sold = sold
        prev_rest = rest

        hold = max(prev_hold, prev_rest - prices[i])
        sold = prev_hold + prices[i]
        rest = max(prev_rest, prev_sold)

    return max(sold, rest)

6. Reconstructing Solutions

Often we need the actual solution, not just the optimal value.

def lcs_with_path(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Backtrack to find LCS
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            lcs.append(s1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(lcs))

7. Tips and Tricks

Recognize DP Problems

"Count ways to..."
"Minimum/maximum..."
"Can you reach/make/achieve..."
"Longest/shortest..."
Choices at each step
Optimal substructure visible

Debug DP

Print the DP table
Verify base cases
Check recurrence on small examples
Ensure correct iteration order

Common Mistakes

Off-by-one errors in indices
Forgetting base cases
Wrong iteration order
Not handling empty input

Exercises

Basic

Find the minimum cost to climb stairs (can climb 1 or 2 steps, each step has a cost).
Count the number of ways to tile a 2×n board with 2×1 tiles.
Find if a sum can be made using array elements (subset sum).

Intermediate

Find the longest palindromic subsequence.
Word Break: Can a string be segmented into dictionary words?
Partition Equal Subset Sum: Can an array be partitioned into two subsets with equal sum?

Advanced

Regular Expression Matching (. and * patterns).
Burst Balloons: Maximize coins from bursting all balloons.
Longest Valid Parentheses: Find length of longest valid parentheses substring.

Summary

DP applies to problems with optimal substructure and overlapping subproblems
Top-down (memoization): Recursive with caching
Bottom-up (tabulation): Iterative, fill table
Framework: Define state, recurrence, base cases, order
Space can often be optimized when only recent states needed
Common patterns: linear, 2D, interval, state machine

Next Reading

Greedy Algorithms →