Dynamic Programming Optimization Patterns: Space Reduction, Bitmask DP, and Interval DP (2025)

1D DP Space Optimization

# Fibonacci: O(n) -> O(1) space
def fib(n: int) -> int:
    if n  int:
    prev2 = prev1 = 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1

# Coin Change (LC 322): only need current row
def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

2D DP Space Optimization – Rolling Array

# LCS: O(m*n) -> O(min(m,n)) space
def lcs(s1: str, s2: str) -> int:
    if len(s1)  int:
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for cap in range(W, w - 1, -1):  # reverse to avoid reuse
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[W]

Bitmask DP – Subset State Representation

# Traveling Salesman Problem (TSP) with bitmask DP
# dp[mask][i] = min cost to visit all cities in mask, ending at city i
def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0

    for mask in range(1 <> u & 1):
                continue
            for v in range(n):
                if mask >> v & 1:
                    continue  # already visited
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])

    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(1, n))
# O(2^n * n^2) time - feasible for n  int:
    n = len(jobs)
    subset_sum = [0] * (1 << n)
    for mask in range(1 <> i & 1:
                subset_sum[mask] = subset_sum[mask ^ (1 << i)] + jobs[i]

    dp = [float('inf')] * (1 << n)
    dp[0] = 0
    for mask in range(1, 1 << n):
        sub = mask
        while sub:
            dp[mask] = min(dp[mask], max(dp[mask ^ sub], subset_sum[sub]))
            sub = (sub - 1) & mask
    return dp[(1 << n) - 1]

Interval DP – Merging Ranges

# Burst Balloons (LC 312): dp[i][j] = max coins from bursting all balloons i..j
def max_coins(nums: list[int]) -> int:
    nums = [1] + nums + [1]  # add boundary sentinels
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):  # interval length
        for left in range(0, n - length):
            right = left + length
            for k in range(left + 1, right):  # last balloon to burst
                dp[left][right] = max(
                    dp[left][right],
                    nums[left] * nums[k] * nums[right] +
                    dp[left][k] + dp[k][right]
                )
    return dp[0][n-1]
# Key insight: think of k as the LAST balloon burst, not first

# Matrix Chain Multiplication: minimum multiplications
def matrix_chain(dims: list[int]) -> int:
    n = len(dims) - 1  # n matrices
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        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]

Meta coding interviews heavily test dynamic programming. Review DP optimization patterns used in Meta interview: dynamic programming problems.

Atlassian coding interviews include DP optimization problems. See common patterns for Atlassian interview: dynamic programming and optimization problems.

Coinbase interviews test DP and combinatorics problems. Review optimization patterns for Coinbase interview: dynamic programming and combinatorics.