Dynamic Programming21 sections · 916 units
Open in Course

Challenge: Three States

Extending to more states

What if there's a cooldown: after robbing a node, you must skip at least one level before robbing again? Now you need three states: (rob,skip1,skip2+)(rob, skip1, skip2+). skip1skip1 = just skipped one level, skip2+skip2+ = skipped two or more.

Transition: rob=value+skip2+childrenrob = value + skip2+_{children}. skip1=robchildrenskip1 = rob_{children}. skip2+=max(skip1,skip2+)childrenskip2+ = \max(skip1, skip2+)_{children}. This pattern generalizes: more constraints = more states. The tree structure stays the same; only the state tuple grows.