Dynamic Programming For Selection Problems
Asked of: Software Engineer
Last updated
What's being tested
These problems test dynamic programming for selection under local conflicts: each choice can block adjacent values or positions. You must reduce the state space, define a correct recurrence, handle take-or-skip decisions, and optimize from O(n) space to O(1) when only the previous states matter.
Patterns & templates
-
Take-or-skip recurrence —
dp[i] = max(dp[i-1], dp[i-2] + value[i]); choosingiexcludes only its immediate predecessor. -
Frequency aggregation — for value-based conflicts, sum all occurrences of each value first, then solve a house-robber DP over sorted or bounded values.
-
Rolling state — track
prev2andprev1instead of an entire table; achieveO(n)time andO(1)auxiliary space. -
Boundary initialization — define empty input as
0, one element as its non-negative value, and avoid indexingi-2before the loop permits it. -
Sparse versus dense values — bounded values support an array; huge sparse domains may require sorting keys, with
O(k log k)preprocessing forkdistinct values. -
Non-negative versus negative inputs — with non-negative values, skipping everything yields
0; if negatives are allowed, explicitly decide whether selecting at least one value is required. -
Proof by invariant — at position
i, maintain that the state stores the best achievable total using only the firstipositions.
Common pitfalls
Pitfall: Treating duplicate values independently in the value-conflict version can violate the rule; aggregate each value’s total before applying adjacency DP.
Pitfall: Greedily taking the largest available value fails because a locally best choice can block two larger combined alternatives.
Pitfall: Confusing adjacent positions with adjacent numeric values; clarify the conflict definition before choosing the DP state.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
Related concepts
- Dynamic Programming, Scheduling, And Set CoverCoding & Algorithms
- Dynamic Programming, Greedy, And Combinatorial OptimizationCoding & Algorithms
- Dynamic Programming and State-Space OptimizationCoding & Algorithms
- Dynamic Programming And MemoizationCoding & Algorithms
- Dynamic Programming And Mutable Range QueriesCoding & Algorithms
- Dynamic Programming, Backtracking, And Combinatorial SearchCoding & Algorithms