Dynamic Programming and State-Space Optimization

What's being tested

These problems test state-space modeling and dynamic programming (DP): defining compact states, transitions, and value propagation under movement and collision constraints. Interviewers probe whether you can exploit invariants (e.g., modulo classes, symmetry) to reduce exponential state blowup and choose the right search/optimization primitive (memoized dfs, bottom-up dp, bfs, or dijkstra).

Patterns & templates

• Bitmask DP for small numbers of tokens — represent occupied cells as bits; typical complexity O(states * transitions) and memory O(2^k * n).

• Canonical ordering: sort token positions (or canonicalize symmetric states) to avoid counting permutations; reduces state-space by k! when tokens indistinguishable.

• Modular invariants: reduce positions using modulo classes (e.g., moves of +3 preserve pos % 3), immediately discarding unreachable targets.

• Use top-down memoization (dfs + cache) for sparse reachable state graphs; bottom-up dp when transition ordering is clear and states dense.

• For weighted single-path problems, use Dijkstra with heapq for min-cost; store predecessor to reconstruct lexicographically tiebroken paths.

• Use BFS for reachability or shortest-step counts on unweighted graphs; complexity O(V+E).

• Tip: prune states with an upper-bound heuristic (e.g., remaining coins max) to speed search when exact optimum needed.

Common pitfalls

Pitfall: Treating identical tokens as distinct causes factorial state explosion; canonicalize positions to collapse equivalent permutations.

Pitfall: Ignoring movement invariants like pos % step == constant leads to wasted work on unreachable states and wrong feasibility answers.

Pitfall: Assuming greedy local coin collection is optimal; without proof, fallback to DP/search and justify complexity tradeoffs.