Dynamic Programming And Memoization
Asked of: Software Engineer
Last updated

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 toO(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 forO(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
Truefor 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.
Featured in interview prep guides
Practice questions
- Maximize weighted subsequence pairs with wildcardsAmazon · Software Engineer · Take-home Project · medium
- Return all valid word-break sentencesAmazon · Software Engineer · Technical Screen · hard
- Solve tree and DP problemsAmazon · Software Engineer · Technical Screen · medium
- Determine string buildability from dictionaryAmazon · Software Engineer · Technical Screen · Medium
- Maximize credits with limited skipsAmazon · Software Engineer · Take-home Project · Medium
- Maximize points with limited coworker skipsAmazon · Software Engineer · Take-home Project · Medium
- Maximize stock profit with constraintsAmazon · Software Engineer · Technical Screen · Medium
- Count expressions reaching a target sumAmazon · Software Engineer · Onsite · Medium
- Determine string segmentability with dictionaryAmazon · Software Engineer · Onsite · Medium
- Find concatenated words in listAmazon · Software Engineer · Technical Screen · Medium
- Design 2D DP on a DAGAmazon · Software Engineer · Technical Screen · Medium
Related concepts
- Dynamic Programming And Mutable Range QueriesCoding & Algorithms
- Dynamic Programming, Backtracking, And Combinatorial SearchCoding & Algorithms
- Dynamic Programming, Backtracking, and State-Space SearchCoding & Algorithms
- Dynamic Programming, Scheduling, And Set CoverCoding & Algorithms
- Dynamic Programming And Combinatorial CountingCoding & Algorithms
- Graph Search, State Space, And Path OptimizationCoding & Algorithms