Beyond the standard DP patterns (knapsack, LCS, linear), advanced DP techniques solve problems that seem intractable at first glance. Bitmask DP compresses set state into integers. Digit DP counts numbers with digit constraints. Tree DP computes optimal values on tree structures. This guide covers these advanced patterns for senior coding interviews and competitive programming.
Bitmask DP
Bitmask DP represents a subset of N elements as an N-bit integer. Bit k is 1 if element k is included, 0 otherwise. This compresses the state space from exponential (all subsets) to 2^N integers, enabling DP over subsets. Traveling Salesman Problem (TSP): find the minimum-cost Hamiltonian path visiting all N cities. State: dp[mask][i] = minimum cost to visit all cities in mask, ending at city i. Transition: dp[mask][i] = min(dp[mask ^ (1 << i)][j] + cost[j][i]) for all j in mask where j != i. Base: dp[1 << start][start] = 0. Answer: min(dp[(1 << N) – 1][i]) for all i. Time: O(2^N * N^2). Feasible for N <= 20. Matching/Assignment: assign N tasks to N workers minimizing total cost. dp[mask] = minimum cost to assign the first popcount(mask) tasks to workers indicated by mask. Transition: dp[mask] = min(dp[mask ^ (1 < 0; sub = (sub – 1) & mask. This visits every subset of mask in decreasing order.
Digit DP
Digit DP counts numbers in a range [L, R] satisfying digit-based constraints. Examples: count numbers from 1 to N with no repeated digits, count numbers from 1 to N whose digit sum equals K, count numbers from 1 to N that are divisible by M. Framework: process digits from the most significant to least significant. State: (position, tight, …constraint-specific state). “tight” tracks whether previous digits exactly match the upper bound — if tight, the current digit is limited to the corresponding digit of N; if not tight, any digit 0-9 is allowed. count(N) gives the answer for [0, N]. count_in_range(L, R) = count(R) – count(L-1). Example — count numbers from 1 to N with digit sum = K: dp[pos][tight][sum] = count of valid numbers. At each position: try each digit d (0 to upper_bound based on tight). Recurse: dp[pos+1][tight AND d == upper_digit][sum + d]. Base case: pos == num_digits and sum == K -> return 1. Memoize on (pos, tight, sum). Time: O(digits * 2 * max_sum * 10). Digit DP is niche but appears in competitive programming and occasionally in senior interviews when the problem involves counting numbers with specific digit properties.
Tree DP
Tree DP computes optimal values on tree structures using DFS. The key insight: a tree rooted at node v has independent subtrees. Process subtrees first (post-order), then combine results at the parent. Maximum Independent Set on a tree: select the maximum set of non-adjacent nodes. dp[v][0] = max independent set in subtree of v when v is NOT selected. dp[v][1] = max independent set when v IS selected. Transition: dp[v][0] = sum(max(dp[child][0], dp[child][1])) for all children — if v is not selected, each child can be either selected or not. dp[v][1] = 1 + sum(dp[child][0]) — if v is selected, no child can be selected. Answer: max(dp[root][0], dp[root][1]). Time: O(N). Tree Diameter: the longest path between any two nodes. dp[v] = longest path starting at v going downward. For each node v: the diameter through v = dp[child1] + dp[child2] (two longest downward paths from v children). Track the global maximum. Binary Tree Camera: minimum cameras to monitor all nodes. dp[v] returns one of three states: monitored (covered by a child camera), has_camera, needs_monitoring. Greedy post-order: if any child needs monitoring, place a camera here. This is tree DP with state transitions based on children states.
Probability and Expected Value DP
Some problems require computing probabilities or expected values through DP. Knight Probability in Chessboard: a knight starts at (r, c) on an N x N board and makes K random moves. What is the probability it stays on the board? dp[k][r][c] = probability of being at (r, c) after k moves while staying on the board. Transition: dp[k][r][c] = sum(dp[k-1][pr][pc] / 8) for all 8 possible previous positions (pr, pc) that can reach (r, c). Base: dp[0][start_r][start_c] = 1. Answer: sum(dp[K][r][c]) for all valid (r, c). Soup Servings: probability that soup A empties before B given random serving operations. dp[a][b] = probability A empties first with a ml of A and b ml of B remaining. New 21 Game: probability of having points <= N after drawing cards until reaching K. dp[i] = probability of reaching exactly i points. Expected value problems: dp[state] = expected cost/time to reach the goal from state. E[state] = sum(probability[action] * (cost[action] + E[next_state])). Solve by working backward from the goal state or using linear equations for cyclic dependencies.
DP Optimization Techniques
When the naive DP is too slow, optimization techniques reduce the time complexity: (1) Space optimization — if dp[i] depends only on dp[i-1], use rolling arrays (two rows instead of N rows). Reduces space from O(NM) to O(M). (2) Monotonic queue optimization — for transitions of the form dp[i] = min(dp[j] + cost(j, i)) where j is in a sliding window. The monotonic deque tracks the optimal j in O(1) amortized. Reduces O(NK) to O(N). (3) Convex hull trick — for transitions dp[i] = min(dp[j] + b[j] * a[i]) where the cost is a product of terms depending on i and j separately. Maintain a convex hull of lines y = b[j] * x + dp[j]. Query the minimum at x = a[i]. Reduces O(N^2) to O(N log N) or O(N) if queries are monotone. (4) Divide and conquer optimization — when the optimal split point is monotone (opt[i] <= opt[i+1]), use divide and conquer to reduce O(NK^2) to O(NK log N). (5) Knuth optimization — for optimal BST / matrix chain problems where the optimal split point satisfies opt[i][j-1] <= opt[i][j] <= opt[i+1][j]. Reduces O(N^3) to O(N^2). These optimizations are primarily competitive programming techniques but may appear in senior interviews at companies like Google or Jane Street.