Dynamic Programming And Combinatorial Counting

What's being tested

These problems test dynamic programming state design, combinatorial counting, and recognizing when a faster mathematical or search-based formulation replaces naive DP. Microsoft interviewers are probing whether you can derive recurrences, prove correctness, handle large constraints, and explain O(...) tradeoffs clearly.

Patterns & templates

• 1D/2D DP recurrence design — define dp[i] or dp[i][j], base cases, transition order, and memory compression when only prior states matter.

• String segmentation DP — dp[i] = any(dp[j] && s[j:i] in dict); optimize with Trie, rolling hash, or max-word-length pruning.

• Interval DP for palindromes — longest palindromic subsequence uses dp[l][r]; fill by increasing substring length, O(n^2) time and space.

• Binary search on answer — for load balancing or capacity minimization, test feasibility greedily in O(n), giving O(n log sum) instead of exponential partitioning.

• Combinatorial divisor counting — transform equations algebraically, factorize N, then count divisors using prime exponents: if $m=\prod p_i^{a_i}$, divisors are $\prod(a_i+1)$.

• Knapsack-style feasibility — distinguish true 0/1 knapsack DP from monotonic feasibility problems where sorting, prefix sums, or binary search is enough.

• Correctness proof template — state invariant, show base case, prove transition/greedy feasibility, then bound time and memory before coding.

Common pitfalls

Pitfall: Jumping to DP without checking monotonicity; many “minimize maximum load” problems are cleaner with binary search plus greedy feasibility.

Pitfall: Counting ordered pairs when the problem asks unordered pairs, or missing symmetry cases like x == y.

Pitfall: Building s[j:i] substrings inside nested loops in languages where slicing copies; this can silently turn O(n^2) into O(n^3).

Practice these

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