The State Definition Problem No One Tells You About
Most dynamic programming failures don't happen because you can't write the recurrence relation. They happen because you defined the wrong state.
I've seen candidates nail the "how do I compute this state from previous states" part but still fail the interview because their state definition created an exponential state space. Or worse, they defined a state that couldn't capture the information needed to make optimal decisions going forward.
The state design step gets maybe 30 seconds in most DP tutorials, sandwiched between "recognize the problem is DP" and "write the recurrence." But in real interviews, this is where you separate yourself from the pack.
Here are 7 state design patterns that actually come up in coding interviews, with the specific cues that tell you which one to use.
Pattern 1: Single-Sequence States When Order Doesn't Matter Forward
The simplest DP states track a single position in a sequence. Use this when:
- Future decisions only depend on "where you are" not "how you got there"
- No need to remember multiple positions simultaneously
- The problem asks about prefixes or suffixes
python
def rob(houses):
"""House Robber: can't rob adjacent houses, maximize loot.
State: dp[i] = max loot using houses[0..i]
Why this works: whether we robbed house i-2 or i-3 doesn't matter,
only the best result we could have achieved before house i.
"""
if not houses:
---
*Continue reading the full article on [TildAlice](https://tildalice.io/dp-state-design-7-patterns-interview/)*
Top comments (0)