Dynamic Programming, Backtracking, and State-Space Search

What's being tested

This tests state modeling: turning coins, tiles, grids, intervals, or circular sequences into compact states with valid transitions. Interviewers look for correct DP recurrence, backtracking pruning, reachability reasoning, and clear complexity analysis before coding.

Patterns & templates

• Top-down DFS + memoization — dfs(state) returns best/possible outcome; cache tuples or encoded counts; usually reduces exponential search dramatically.

• Bottom-up DP recurrence — define dp[i], dp[r][c], or dp[mask]; prove transition order and base cases before writing loops.

• Backtracking over multisets — use counts[value], choose first nonzero item, try legal groups, undo mutations; avoids permuting equivalent arrangements.

• Reachability graph on implicit states — generate neighbors on demand instead of materializing graph; use visited for feasibility, dp for optimization.

• Circular array normalization — duplicate array/string or fix a cut point; handle wraparound carefully and validate parity/count feasibility first.

• Space optimization — compress grid/path DP from O(mn) to O(n) when transitions only depend on previous row or few prior states.

• Interval scheduling DP/greedy split — sort by end/start time, use binary search via bisect_left; compare O(n log n) optimized versus simpler O(n^2).

Common pitfalls

Pitfall: Starting with recursion over raw permutations instead of canonical states causes duplicate work and timeouts on tile/multiset problems.

Pitfall: Forgetting base cases such as empty hand, zero coins, blocked start/end cell, or impossible odd counts leads to almost-correct solutions.

Pitfall: Giving only an algorithm name is not enough; state definition, transition, answer extraction, and complexity must be explicit.