🌳 Advanced DP: Tree and Bitmask DP
The Magical Forest of Decisions
Imagine you’re a wise owl 🦉 flying through a magical forest. Each tree has branches, and each branch leads to other branches. Sometimes you need to make choices at every branch—and the best choice depends on what your “children branches” decided!
That’s Dynamic Programming on Trees and Bitmask DP. Let’s explore this enchanted forest together!
🌲 Part 1: DP on Trees
What is DP on Trees?
Think of a family tree. Grandparents at the top, then parents, then kids at the bottom.
DP on Trees means:
- Start from the leaves (the kids at the bottom)
- Work your way up to the root (grandparents)
- Each node makes decisions based on what its children decided
Grandpa (Root)
/ \
Mom Uncle
/ \ |
You Sister Cousin
(leaf) (leaf) (leaf)
Simple Rule: Solve for leaves first, then their parents, then grandparents!
Why Use DP on Trees?
Real-Life Example:
You’re choosing paint colors for rooms. Each room connects to others:
- Hallway connects to Kitchen and Bedroom
- You can’t paint connected rooms the same color!
This is a tree constraint problem—and DP on trees solves it beautifully!
How It Works: Step by Step
graph TD A["Start at Leaves"] --> B["Calculate leaf values"] B --> C["Move to parents"] C --> D[Combine children's answers] D --> E["Repeat until root"] E --> F["Root has final answer!"]
The Pattern:
def dfs(node, parent):
# Base: calculate for this node
result = base_value(node)
# Combine all children's results
for child in children[node]:
if child != parent:
child_result = dfs(child, node)
result = combine(result, child_result)
return result
🏠 Part 2: House Robber III
The Story
You’re a clever raccoon 🦝 in a neighborhood. Houses are arranged like a tree—each house connects to child houses below it.
The Rules:
- If you visit a house, you collect its coins
- You CAN’T visit a house AND its direct children
- Find the MAXIMUM coins you can collect!
House A (3 coins)
/ \
House B (4) House C (5)
/ \ \
House D(1) House E(3) House F(1)
Wrong approach: Visit A, D, E, F = 3+1+3+1 = 8 coins Better: Skip A, visit B, C = 4+5 = 9 coins Best: Visit A, D, E, F = 3+1+3+1 = 8? Wait… Actually: Visit B and C = 4+5 = 9 coins ✨
The Magic Solution
For EACH house, we track TWO values:
- WITH this house → coins if we rob it
- WITHOUT this house → coins if we skip it
def rob_tree(node):
if node is None:
return (0, 0) # (with, without)
# Ask children what they found
left = rob_tree(node.left)
right = rob_tree(node.right)
# If we rob THIS house:
# We CANNOT rob children
with_node = node.coins + left[1] + right[1]
# If we SKIP this house:
# Children can be robbed OR skipped
without_node = max(left) + max(right)
return (with_node, without_node)
# Answer is max of root's two options
answer = max(rob_tree(root))
Visual Walkthrough
graph TD A["🏠 3 coins"] --> B["🏠 4 coins"] A --> C["🏠 5 coins"] B --> D["🏠 1 coin"] B --> E["🏠 3 coins"] C --> F["🏠 1 coin"] style A fill:#FFD700 style B fill:#90EE90 style C fill:#90EE90
Step by step:
- Leaves (D, E, F): Each returns (coins, 0)
- B: with=4+0+0=4, without=1+3=4
- C: with=5+0=5, without=1=1
- A: with=3+4+1=8, without=4+5=9
Answer: 9 coins! 🎉
🎭 Part 3: DP with Bitmasks
What is a Bitmask?
Imagine you have 4 friends: Alice, Bob, Carol, Dave.
Instead of writing [“Alice”, “Bob”], we use bits:
- Alice = position 0 → bit value 1
- Bob = position 1 → bit value 2
- Carol = position 2 → bit value 4
- Dave = position 3 → bit value 8
Example Masks:
0000 (0) = nobody
0001 (1) = Alice
0011 (3) = Alice + Bob
1111 (15) = everyone!
Why Use Bitmasks?
Speed and Simplicity!
Instead of lists and sets, we use simple numbers:
- Check if Bob is included:
mask & (1 << 1) - Add Carol:
mask | (1 << 2) - Remove Dave:
mask & ~(1 << 3)
# Check if person i is in the mask
def has_person(mask, i):
return mask & (1 << i) != 0
# Add person i to mask
def add_person(mask, i):
return mask | (1 << i)
# Remove person i from mask
def remove_person(mask, i):
return mask & ~(1 << i)
Bitmask DP Pattern
The Classic Problem: Traveling Salesperson
Visit all N cities exactly once, return home, minimize distance.
# dp[mask][i] = min cost to visit cities
# in mask, ending at city i
def tsp(n, dist):
INF = float('inf')
dp = [[INF] * n for _ in range(1 << n)]
# Start at city 0
dp[1][0] = 0
for mask in range(1 << n):
for last in range(n):
if dp[mask][last] == INF:
continue
# Try visiting each unvisited city
for next_city in range(n):
if mask & (1 << next_city):
continue # Already visited
new_mask = mask | (1 << next_city)
new_cost = dp[mask][last] + dist[last][next_city]
dp[new_mask][next_city] = min(
dp[new_mask][next_city],
new_cost
)
# Return to start
full = (1 << n) - 1
return min(dp[full][i] + dist[i][0]
for i in range(n))
When to Use Bitmask DP?
✅ Use when:
- N is small (≤ 20, ideally ≤ 15)
- Need to track “which items are used”
- Subset problems with constraints
❌ Don’t use when:
- N is large (2^N explodes!)
- Simple counting suffices
🎁 Part 4: Subsets Using Bitmasks
The Subset Superpower
Every number from 0 to 2^N-1 represents a unique subset!
For N=3 (items A, B, C):
000 (0) = {}
001 (1) = {A}
010 (2) = {B}
011 (3) = {A, B}
100 (4) = {C}
101 (5) = {A, C}
110 (6) = {B, C}
111 (7) = {A, B, C}
Generating All Subsets
def all_subsets(items):
n = len(items)
subsets = []
for mask in range(1 << n):
subset = []
for i in range(n):
if mask & (1 << i):
subset.append(items[i])
subsets.append(subset)
return subsets
# Example
print(all_subsets(['A', 'B', 'C']))
# [[], ['A'], ['B'], ['A','B'],
# ['C'], ['A','C'], ['B','C'], ['A','B','C']]
Subset Sum with Bitmasks
Problem: Can you pick items that sum to target?
def subset_sum(nums, target):
n = len(nums)
for mask in range(1 << n):
total = 0
for i in range(n):
if mask & (1 << i):
total += nums[i]
if total == target:
return True
return False
# Example
print(subset_sum([3, 1, 4, 2], 6)) # True: 3+1+2
Iterating Over Submasks
Pro Trick: Loop through all submasks of a mask!
def all_submasks(mask):
submasks = []
sub = mask
while sub > 0:
submasks.append(sub)
sub = (sub - 1) & mask
submasks.append(0) # Empty subset
return submasks
# Example: submasks of 5 (101 binary)
# Returns: [5, 4, 1, 0] → {A,C}, {C}, {A}, {}
Why it works:
(sub - 1) & mask cleverly jumps to the next valid submask!
🧠 Putting It All Together
Tree + Bitmask Combined!
Sometimes trees have special constraints that need bitmasks.
Example: Assign K colors to tree nodes, no adjacent same colors.
def color_tree(node, parent_color, k):
"""
For each node, try all colors
except parent's color.
Use bitmask to track available colors.
"""
available = ((1 << k) - 1) ^ (1 << parent_color)
total_ways = 0
for color in range(k):
if available & (1 << color):
ways = 1
for child in node.children:
ways *= color_tree(child, color, k)
total_ways += ways
return total_ways
🎯 Key Takeaways
graph TD A["Advanced DP"] --> B["Tree DP"] A --> C["Bitmask DP"] B --> D["Bottom-up on tree"] B --> E["House Robber III"] C --> F["Subset tracking"] C --> G["All subsets: 0 to 2^n-1"] style A fill:#FFD700 style B fill:#87CEEB style C fill:#98FB98
Remember:
- Tree DP = Solve leaves first, combine upward
- House Robber = Track (with, without) for each node
- Bitmask = Use bits to represent sets
- Subsets = Loop 0 to 2^N-1 to get all subsets
🌟 You Did It!
You’ve just learned some of the most powerful DP techniques used in competitive programming!
These patterns appear in:
- Job scheduling on hierarchies
- Game theory problems
- Network optimization
- And countless coding interviews!
Practice makes perfect. Start with simple tree problems, then add bitmask complexity. Soon, these will feel like second nature! 🚀