Dynamic Programming And Memoization

What's being tested

Dynamic programming here means recognizing overlapping subproblems, defining a compact state, and proving the recurrence before coding. Interviewers are probing whether you can move between top-down memoization, bottom-up tabulation, graph ordering, and string segmentation without double-counting or exponential blowups.

Patterns & templates

• Top-down memoization with `dfs(i, remaining)` or `dfs(index)` — cache states in `dict`; usually reduces exponential recursion to O(states * transition_cost).

• Subset-sum/count DP — transform target-sign problems into sum(P) = (total + target) / 2; handle parity, negative targets, and zeros carefully.

• Word break DP — dp[i] = any(dp[j] and s[j:i] in words); O(n^2) substrings, often improved with max word length.

• Trie-guided segmentation — walk forward from each valid `i` through a `Trie`; avoids checking impossible prefixes and reduces wasted substring hashing.

• DAG dynamic programming — process nodes in topological order; for bounded path length use dp[steps][node] or rolling arrays for O(V) space.

• Concatenated words template — sort by length, build a `set` incrementally, and run word-break while preventing the whole word from counting as itself.

• Counting vs existence — sum(...) for number of ways, any(...) for feasibility, parent/backtracking arrays for producing actual segmentations.

Common pitfalls

Pitfall: Treating zeros like normal numbers in target-sum counting; each zero doubles the number of valid expressions.

Pitfall: Using plain recursion for word segmentation or DAG paths; without memoization, repeated suffixes or subpaths explode exponentially.

Pitfall: Returning True for a concatenated word because it exists in the dictionary; require at least two smaller component words.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.