Counting and Bitmask DP
What is this?
Two of these problems have a transition that sums a whole range of earlier states. That is correct, and too slow. Both collapse to a sliding window by writing the recurrence twice and subtracting. The other three are about state: a ± assignment problem that turns out to be subset sum, and two searches whose state is "what still needs covering" (a bitmask of covered target positions for Stickers, a start index for Word Break II) rather than a position in an input.
Fun fact: Target Sum asks how many ways to put
+or−in front of each number to reach a target, and looks like2ⁿenumeration. LetPbe the numbers you make positive andNthe rest. ThenP − N = targetandP + N = total, soP = (total + target) / 2and that is a fixed number. The question collapses to "how many subsets sum toP", an ordinary 0/1 knapsack count. As a bonus, two cheap checks answer0at once:total + targetodd (parity), or|target| > total(out of range). Turning a signed-assignment problem into a subset sum by adding the two equations is a move worth keeping.
🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: if a transition sums many earlier states, write it for
kand fork−1and subtract. Nearly every term cancels, and an entire dimension of work disappears.
1. Collapse the sum
The natural recurrence for K Inverse Pairs (inserting the n-th element can create 0 to n−1 new inversions) is a range sum:
dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + … + dp[n-1][k-n+1]
Write the same line for k−1 and subtract. Everything cancels except the two edges:
dp[n][k] = dp[n][k-1] + dp[n-1][k] - dp[n-1][k-n]
O(n²k) becomes O(nk) time, and keeping only the previous row gives O(k) space. Two details bite: dp[n-1][k-n] only exists when k ≥ n, and the subtraction can go negative before the modulo, so normalise after every step.
2. The same move, as a window
New 21 Game draws uniformly from 1 … maxPts while below k, and asks for the probability of finishing at or below n (the problem guarantees k ≤ n). Each state is the mean of the previous maxPts states, the same summed transition, so the same fix:
dp[0], window, ans = 1.0, 1.0, 0.0
for i in range(1, n + 1):
dp[i] = window / maxPts
if i < k: window += dp[i] # still drawing
else: ans += dp[i] # stopped here, and it counts
if 0 <= i - maxPts < k: window -= dp[i-maxPts] # slide the window
The guard is exact: a state leaves the window only if it was ever in it, which requires i - maxPts < k. The early exit if k == 0 or n >= k + maxPts - 1: return 1.0 handles the case where every possible final score is already at most n, so the answer is certain. Time is O(n); the dp array is O(n) space, and only the last maxPts values are ever read, so a ring buffer brings it to O(maxPts).
3. State that is "what remains"
Stickers to Spell Word uses a bitmask over the target's positions. dp[mask] is the fewest stickers still needed when the positions in mask are already covered:
@lru_cache(None)
def dp(mask):
if mask == FULL: return 0
i = lowest_uncovered(mask) # this position must be covered by SOME sticker
for cnt in sticker_counts:
if cnt[target[i]] == 0: continue # the pruning that makes it feasible
... # apply the sticker greedily, recurse on the new mask
Requiring every candidate sticker to contain the letter at the lowest uncovered position prunes the branching and costs nothing in correctness: that position has to be covered by some sticker, and the stickers of a solution can be applied in any order. Each transition covers at least that position, so the mask always grows. With n = len(target) there are at most 2ⁿ masks and each tries every sticker over the target, so time is O(2ⁿ · stickers · n) and space is O(2ⁿ). The small limit on the target length is what makes 2ⁿ states acceptable. If a needed letter appears in no sticker the answer is -1.
Word Break II is the same idea over suffixes. solve(start) returns the list of sentences that segment s[start:], memoised on the start index, rather than a count. Memoising stops the same suffix from being re-expanded for every prefix that reaches it, and a Word Break I reachability pass stops it from entering suffixes that cannot be segmented. The scans cost O(n³) in total, and building the sentences costs time proportional to their total size. That size can be exponential: for "aaaa…" with every run of as in the dictionary there are 2ⁿ⁻¹ sentences. That is a property of the question, not of the method.
4. A 30-second worked example (Target Sum)
nums = [1,1,1,1,1], target = 3
Two checks save the most time, and they fail for different reasons. With target = 2, total + target = 7 is odd, so P is not an integer and the answer is 0 (parity). With target = 7, total + target = 12 is even and P = 6, yet |target| > total means no assignment can reach it, so the answer is 0 (out of range). Either way the answer is 0 before a table is allocated.
5. Where you'll actually meet this
- Probability under a stopping rule. New 21 Game is a bounded random walk that halts at a threshold, a small Markov chain.
- Covering an order from packs. Stickers has the shape of "cover this requirement from these bundles using as few as possible", though real packing problems are rarely this small.
- Text segmentation. Word Break II lists every way to split a string into dictionary words, the same task as segmenting text written without spaces.
- Ranking comparison. Inversion counts measure how far one ordering is from another.
- Exact-sum counting. Counting subsets that hit a fixed total is the same table as Target Sum.
6. Problems in this chapter
K Inverse Pairs Array
Count arrays with exactly k inverse pairs. The summed transition collapses to three terms by differencing adjacent states.
Pattern: counting DP with a collapsed range sum. Target: O(nk) time, O(k) space with two rolling rows.
New 21 Game
Probability of stopping at or below n. Each state is the mean of a fixed window of earlier states, maintained as a running sum.
Pattern: probability DP with a sliding window. Target: O(n) time, O(n) space (O(maxPts) with a ring buffer).
Target Sum
Count ± assignments reaching a target. Solve for the positive subset's sum and count subsets that reach it.
Pattern: subset-sum counting. Target: O(n · sum) time, O(sum) space.
Stickers to Spell Word
Fewest stickers spelling a target. Keep a bitmask of covered target positions and only try stickers containing the lowest uncovered letter.
Pattern: bitmask DP with memo. Target: O(2ⁿ · stickers · n) time, O(2ⁿ) space, n = len(target).
Word Break II
Every sentence formable from the dictionary. Memoise on the start index and return the list of completions of each suffix.
Pattern: memoised backtracking over suffixes. Target: O(n³) scans plus output-bound sentence building, and the output can reach 2ⁿ⁻¹.
7. Common pitfalls
- Leaving the summed transition in place. It passes the samples and times out on the real constraints.
- Reading
dp[n-1][k-n]whenk < n. That term does not exist and must be guarded. - Taking a modulo of a negative. Normalise after every subtraction.
- Sliding the probability window unconditionally. A state only leaves if it ever entered, which needs
i - maxPts < k. - Skipping the Target Sum feasibility checks. Parity (
total + targetodd) and range (|target| > total) are different failures, and both mean0immediately. - Reading Stickers'
dp[mask]backwards. It is the number of stickers still needed from that state, withdp[FULL] = 0. - Dropping the lowest-uncovered-letter pruning, which is the difference between fast and hopeless.
- Calling Word Break II polynomial. The scans are
O(n³), but the sentences you build can be exponentially many.
8. Key takeaways
- A summed transition is a signal, not a solution. Difference adjacent states and it collapses.
- A sliding window is the same trick wearing a probability hat.
- Add the two equations.
P − N = targetwithP + N = totalturns signs into a subset sum. - State can be "what is left" rather than "how far you have come".
- Pick a compact memo key. A bitmask of covered positions (Stickers) or a start index (Word Break II) lets equivalent states share one entry.
- A forced-coverage pruning is free correctness: the lowest uncovered position must be covered by some sticker, so only try stickers that can.
- Why interviewers like it: the naive recurrence is easy and quadratic, so the optimisation is precisely the thing being measured.
Order: K Inverse Pairs Array → New 21 Game → Target Sum → Stickers to Spell Word → Word Break II.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson