Recursion & DP Target: 15s
Bitmask DP: represent subset as integer, each bit = included/excluded. O(2^n * n). For n ≤ 20.
def bitmaskDP(n, cost):
# dp[mask] = best answer using subset 'mask'
dp = [float('inf')] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == float('inf'): continue
for i in range(n):
if mask & (1 << i): continue # already used
new_mask = mask | (1 << i)
bits = bin(mask).count('1') # position = items used so far
dp[new_mask] = min(dp[new_mask],
dp[mask] + cost[bits][i])
return dp[(1 << n) - 1]Type it from memory. Go.