Interview conceptCoding & Algorithms

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]); choosing i excludes 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 prev2 and prev1 instead of an entire table; achieve O(n) time and O(1) auxiliary space.

  • Boundary initialization — define empty input as 0, one element as its non-negative value, and avoid indexing i-2 before 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 for k distinct 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 first i positions.

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