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 -12D 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]
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you reduce space complexity in 2D dynamic programming?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a rolling array: instead of storing the entire m x n DP table, only keep the previous row (or two rows for some problems). For LCS and edit distance, only the previous row is needed, reducing O(m*n) to O(min(m,n)) space. For 0/1 knapsack, iterate the capacity dimension in reverse order to reuse a single 1D array – the reverse iteration ensures each item is only used once. Always check if the DP recurrence only depends on a fixed number of previous states to determine how much space you can save.”}},{“@type”:”Question”,”name”:”What is bitmask DP and when should you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Bitmask DP represents a subset of n elements as an integer bitmask where bit i is set if element i is included. It is used when n is small (typically n <= 20) and you need to track which subset of elements has been processed. Common problems: Traveling Salesman Problem (dp[mask][i] = min cost visiting cities in mask ending at i), task assignment, minimum cost to connect all nodes. Time complexity is O(2^n * n) or O(2^n * n^2), so only feasible for small n.”}},{“@type”:”Question”,”name”:”What is interval DP and when is it applied?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Interval DP solves problems by building solutions for larger intervals from solutions to smaller sub-intervals. The state dp[i][j] represents the answer for the subarray/interval from index i to j. Iteration: enumerate interval lengths from 2 to n, then all starting positions, then a split point k within the interval. Classic problems: Burst Balloons (LC 312), Matrix Chain Multiplication, Optimal Binary Search Tree, and Palindrome Partitioning II. Key insight for Burst Balloons: think of k as the LAST balloon burst in interval [i,j], not the first.”}},{“@type”:”Question”,”name”:”How do you recognize when to use DP vs greedy vs backtracking?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use DP when: the problem has overlapping subproblems (same subproblems solved multiple times) and optimal substructure (global optimum built from local optima). Use greedy when: a locally optimal choice leads to a globally optimal solution (proven by exchange argument) – e.g., activity selection, Huffman coding. Use backtracking when: you need all solutions or the problem has constraints that prune the search space – e.g., N-queens, permutations, combination sum. The DP indicator: can you express the answer as a function of answers to smaller subproblems with a clear recurrence?”}},{“@type”:”Question”,”name”:”How does the 0/1 knapsack DP differ from the unbounded knapsack?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”In 0/1 knapsack, each item can be used at most once. The key technique: iterate the capacity dimension in reverse order (from W down to w) when updating the DP array. This ensures that dp[cap – w] reflects the state before adding item i, so each item is counted at most once. In unbounded knapsack, each item can be used multiple times. Iterate capacity in forward order (from w up to W) – this allows using the same item multiple times within the same pass. Coin Change (LC 322) is unbounded knapsack; 0/1 Knapsack (classic problem) uses reverse iteration.”}}]}
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.