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

Source: https://www.techinterview.org/post/3233466552/dynamic-programming-optimization/
Updated: 2026-07-05 · techinterview.org

## 1D DP Space Optimization


```
# Fibonacci: O(n) -> O(1) space
def fib(n: int) -> int:
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

# House Robber (LC 198): no two adjacent houses
def rob(nums: list[int]) -> 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) < len(s2):
        s1, s2 = s2, s1  # ensure s2 is the shorter string
    prev = [0] * (len(s2) + 1)
    for c1 in s1:
        curr = [0] * (len(s2) + 1)
        for j, c2 in enumerate(s2):
            if c1 == c2:
                curr[j + 1] = prev[j] + 1
            else:
                curr[j + 1] = max(prev[j + 1], curr[j])
        prev = curr
    return prev[len(s2)]

# 0/1 Knapsack: 2D -> 1D rolling array
def knapsack(weights: list[int], values: list[int], W: int) -> 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](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/).

Atlassian coding interviews include DP optimization problems. See common patterns for [Atlassian interview: dynamic programming and optimization problems](https://www.techinterview.org/post/3233459919/atlassian-interview/).

Coinbase interviews test DP and combinatorics problems. Review optimization patterns for [Coinbase interview: dynamic programming and combinatorics](https://www.techinterview.org/post/3233459920/coinbase-interview/).