Counting DP: Counting Every Object Exactly Once

Counting DP answers "how many ways" questions: the number of paths, decodings, sequences or partitions that satisfy a rule. It looks like optimization DP with max replaced by +, but it has one extra requirement that causes most of the bugs: every object must be counted exactly once.

Intuition

To count a set S that is far too large to list, split it into pieces that are easier to count and add up their sizes. For the sum to be correct, the pieces must be:

• disjoint: no object lands in two pieces (otherwise it is double counted), and
• exhaustive: every object lands in some piece (otherwise it is missed).

With max or min, overlapping pieces are harmless: taking a maximum twice changes nothing. With + they are fatal. The standard way to get a clean split is to classify objects by one decisive feature, usually the last step: the last part of a sum, the last move into a cell, the length of the last chunk. Each object has exactly one last step, so the classes are automatically disjoint and exhaustive.

A worked example. How many ways can n be written as an ordered sum of k positive integers? Classify by the last part x: it is one of 1..n, and removing it leaves an ordered sum of n - x with k - 1 parts. So f[n][k] = sum of f[n - x][k - 1] for x = 1..n, with f[0][0] = 1 (the empty sum).

def count_compositions(n: int, k: int) -> int:
    # f[s][j] = ways to write s as an ordered sum of j positive parts
    f = [[0] * (k + 1) for _ in range(n + 1)]
    f[0][0] = 1
    for j in range(1, k + 1):
        for s in range(1, n + 1):
            # classify by the value of the last part, which is exactly one of 1..s
            f[s][j] = sum(f[s - last][j - 1] for last in range(1, s + 1))
    return f[n][k]

(The closed form is C(n-1, k-1), a good sanity check.)

Ordered vs unordered

If order does not matter (4 = 1 + 3 and 4 = 3 + 1 are the same partition), "classify by the last part" double counts, because one multiset has many orders. Fix an order instead: list parts in non-decreasing order, or equivalently decide how many times each part size is used, one size at a time. The partitions of n with parts at most m either use no part m, or use at least one (remove it): p(n, m) = p(n, m - 1) + p(n - m, m). Kept in a single array, that is exactly the coin-change loop with part sizes in the outer loop:

def count_partitions(n: int) -> int:
    # p[s] = ways to write s as an unordered sum of the part sizes introduced so far
    p = [1] + [0] * n
    for part in range(1, n + 1):  # introduce part sizes one at a time
        for s in range(part, n + 1):
            p[s] += p[s - part]
    return p[n]

Swapping the loops (sum outside, part inside) counts ordered sums instead. Whenever you write a counting DP, ask: "would two different orders of the same choices be counted separately, and should they be?"

When to use it in interviews / OAs

• "Return the number of ways ..., modulo 10^9 + 7". The modulus alone tells you the answer is huge and must be counted, not enumerated.
• Paths in a grid or a DAG, decodings of a string, tilings, sequences of moves or rolls with a target total.
• Brute force would list objects one by one, but they share long common prefixes or suffixes.

Templates

Decodings of a digit string ("1" to "26" map to letters). Classify by the length of the last chunk: 1 digit (must not be "0") or 2 digits (must be between "10" and "26").

def decode_ways(s: str) -> int:
    n = len(s)
    f = [1] + [0] * n  # f[i] = ways to decode s[:i]; the empty prefix decodes one way
    for i in range(1, n + 1):
        if s[i - 1] != "0":  # last chunk has one digit
            f[i] += f[i - 1]
        if i >= 2 and "10" <= s[i - 2:i] <= "26":  # last chunk has two digits
            f[i] += f[i - 2]
    return f[n]

Paths in a grid with obstacles (moves go right or down). Classify by the last move: from above or from the left. One row of memory suffices: before the update, ways[c] still holds the value from the row above.

def unique_paths(grid: list[list[int]]) -> int:
    # grid[r][c] == 1 marks a blocked cell
    cols = len(grid[0])
    ways = [0] * cols
    ways[0] = 1  # one way to "enter" the start cell from above
    for row in grid:
        for c in range(cols):
            if row[c]:
                ways[c] = 0
            elif c:
                ways[c] += ways[c - 1]  # from above (old ways[c]) plus from the left
    return ways[-1]

Dice summing to a target. Each die contributes exactly one face, so every die is a group from which exactly one item is taken; a fresh array per die enforces that.

MOD = 10**9 + 7


def dice_rolls(n: int, k: int, target: int) -> int:
    f = [1] + [0] * target  # f[s] = ways for the dice rolled so far to sum to s
    for _ in range(n):
        g = [0] * (target + 1)
        for s in range(1, target + 1):
            g[s] = sum(f[s - face] for face in range(1, min(k, s) + 1)) % MOD
        f = g
    return f[target]

The inner sum is a window of k consecutive entries of f, so prefix sums bring the cost from O(n * target * k) down to O(n * target).

Complexity

States times transitions per state, as with any DP: compositions O(n^2 * k) (O(n * k) with prefix sums), partitions O(n^2), decode ways O(n), grid paths O(rows * cols), dice O(n * target * k). Space can almost always be reduced to one or two rows.

Common pitfalls

• Overlapping classes: classifying by something that is not unique per object (for instance "contains a 2") double counts. Classify by a feature every object has exactly one of.
• Order confusion: decide up front whether order matters; the loop nesting is what encodes it.
• Base case: the empty object counts as one way (f[0] = 1). Using 0 makes everything 0.
• Modulo: apply it after each addition. In C++/Java, after a subtraction add the modulus back before taking % so the result is non-negative; use 64-bit types for products.
• Zeros in decodings: "0" alone is invalid, "06" is not 6, and "10"/"20" are valid only as two-digit chunks.

Interview variations

• Climbing stairs with steps of 1 or 2: ordered compositions with restricted parts.
• Coin change II (unordered) vs combination sum IV (ordered): same items, different loop order.
• Unique paths, with obstacles, or with a required cell (multiply the counts of the two halves).
• Knight dialer, count walks of length n on a small graph: state = current node, one step per round.
• Domino and tromino tilings, painting an n x 3 grid: classify by the shape or coloring of the last column.
• Number of music playlists: classify by whether the last song is new or a repeat.
• Count strings of a given length built from pieces of fixed lengths: ordered compositions with allowed part sizes.