Dynamic Programming21 sections · 916 units
Open in Course

Pattern - Adjacent Blocking

The common structure

House Robber and Boredom share a pattern: taking an element blocks its neighbors. This creates a "skip or take" decision at each position.

The general recurrence is dp[i]=max(dp[i1],dp[i2]+value[i])dp[i] = \max(dp[i-1], dp[i-2] + value[i]). Skip position ii (keep previous best) or take position ii (add value to best from two back). Variations include: different blocking rules (block next 22 instead of 11), different values (constant vs variable), and reconstruction (tracking which elements were taken).

When you see a problem where taking one thing prevents taking nearby things, try mapping it to this pattern. The reduction often makes the solution obvious.