Dynamic Programming

Dynamic Programming (DP) is an optimization technique for problems with overlapping subproblems and optimal substructure. Instead of solving the same subproblem repeatedly, DP stores results in a table (memoization or tabulation) and reuses them.

Memoization (Top-Down)

Memoization is recursion with caching. We write a recursive function that solves the problem, but before computing a result we check a cache (usually a dictionary or array). If the result is already cached, return it; otherwise compute and store it.

def fib_memo(n, 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]

Tabulation (Bottom-Up)

Tabulation solves the problem iteratively by filling a table from the smallest subproblems upward. This avoids recursion entirely and is usually more efficient in both time and space.

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]

# Space-optimized O(1) version
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Classic DP Problems

1. 0/1 Knapsack

Given weights and values of n items, and a capacity W, choose items to maximize total value without exceeding capacity. Each item can be taken at most once.

def knapsack_01(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) or O(W) with 1D optimization.

2. Longest Common Subsequence (LCS)

Given two strings X and Y, find the length of the longest subsequence common to both. Subsequences preserve order but not necessarily contiguity.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Time: O(mn), Space: O(mn) or O(min(m, n)) with space optimization.

3. Longest Increasing Subsequence (LIS)

Find the length of the longest subsequence of a given array where elements are strictly increasing.

def lis(arr):
    n = len(arr)
    dp = [1] * n
    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) using patience sorting
def lis_optimized(arr):
    import bisect
    tails = []
    for x in arr:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

4. Edit Distance (Levenshtein Distance)

Compute the minimum number of operations (insert, delete, replace) needed to transform one string into another.

def edit_distance(A, B):
    m, n = len(A), len(B)
    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 A[i - 1] == B[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]

Time: O(mn), Space: O(mn) or O(n).

DP vs Recursion vs Greedy