Counting and Bitmask DP

What is this?

Two of these problems have a transition that sums a whole range of earlier states — which 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" rather than an index.

💡 Fun fact: Target Sum asks how many ways to put + or − in front of each number to reach a target, and looks like 2ⁿ enumeration. Let P be the numbers you make positive and N the rest. Then P − N = target and P + N = total, so P = (total + target) / 2 — a fixed number. The question collapses to "how many subsets sum to P", an ordinary 0/1 knapsack count. As a bonus, if total + target is odd or |target| > total the answer is instantly 0. 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.

The one-line idea: if a transition sums many earlier states, write it for k and for k−1 and 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) and the code shrinks. 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. 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 stopping below n is certain — and skipping it leaves an array of size n that is never needed.

3. State that is "what remains"

Stickers to Spell Word memoises on the sorted remaining letters, not on an index:

@lru_cache(None)
def go(rem):
    if not rem: return 0
    first = rem[0]                                 # must be covered by SOME sticker
    for c in counts:
        if c[first] == 0: continue                 # ← the pruning that makes it feasible
        ...

Requiring every candidate sticker to contain rem[0] prunes enormously and costs nothing in correctness — that letter has to come from somewhere, so trying stickers that cannot supply it only re-derives orderings already explored. Sorting the remainder is what makes two equivalent states hash to the same key.

Word Break II is the same idea over suffixes, memoised on the start index, returning the list of sentences rather than a count. Memoising is what keeps a string like "aaaaaaaa" with dictionary ["a","aa","aaa"] from re-deriving the same suffix repeatedly — though the output can still be exponential, which is a property of the question.

4. A 30-second worked example (Target Sum)

nums = [1,1,1,1,1], target = 3

total = 5,  target = 3
total + target = 8, even  ✓        P = 8 / 2 = 4

so: how many subsets of [1,1,1,1,1] sum to 4?
    choose 4 of the 5 ones → C(5,4) = 5

answer: 5      (and indeed +1+1+1+1−1 and its four rearrangements)

The check that saves the most time is the parity one. With target = 2, total + target = 7 is odd, no subset sum exists, and the answer is 0 before a table is allocated — a fact no amount of enumeration would have discovered as quickly.

5. Where you'll actually meet this

• Risk and gaming systems. New 21 Game is a bounded random walk, which is how ruin probabilities are actually computed.
• Inventory and fulfilment. Stickers is "cover this order from these packs, using as few as possible".
• Search and autocomplete. Word Break II is segmentation for languages written without spaces.
• Ranking and sorting analysis. Inversion counts measure how far a ranking is from a reference.
• Budget and portfolio allocation. Subset-sum counting underlies "how many ways can this be funded exactly".

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.

▶ 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.

▶ 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. Memoise on the sorted remaining letters and only try stickers covering the first one.
Pattern: memoised search over remaining state. Target: exponential worst case, fast with the pruning.

▶ 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. Target: output-bound.

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] when k < 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 — i - maxPts < k.
• Missing the parity check in Target Sum, which decides many inputs instantly.
• Memoising stickers on an unsorted remainder, so equivalent states never share a cache entry.
• Dropping the first-letter pruning, which is the difference between fast and hopeless.

8. Key takeaways

1. A summed transition is a signal, not a solution. Difference adjacent states and it collapses.
2. A sliding window is the same trick wearing a probability hat.
3. Add the two equations. P − N = target with P + N = total turns signs into a subset sum.
4. State can be "what is left" rather than "how far you have come".
5. Canonicalise the memo key — sort the remainder, or equivalent states never merge.
6. A forced-coverage pruning is free correctness: the first uncovered letter must come from somewhere.
7. 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.