13.15 Counting Dynamic Programming

Many dynamic programming problems ask for the best solution:

minimum cost

maximum value

shortest path

Counting dynamic programming asks a different question:

How many valid solutions exist?

Instead of searching for an optimum, we count every valid configuration while avoiding duplicate work. The resulting techniques appear throughout combinatorics, graph theory, string algorithms, probability, scheduling, cryptography, and competitive programming.

Counting problems are often deceptively difficult. Enumerating all solutions may require exponential time, but dynamic programming can frequently count them in polynomial time by recognizing overlapping subproblems.

The key insight is that we usually do not need to generate every solution. We only need to know how many there are.

Problem

How do we count large numbers of valid solutions without explicitly generating them?

Understanding Counting States

The most common state meaning is:

$$ dp[state] $$

Meaning:

The number of valid ways to reach or construct this state.

Examples:

number of paths

number of partitions

number of subsequences

number of schedules

number of valid configurations

Unlike optimization DP:

take minimum

take maximum

counting DP usually combines transitions using addition.

This simple observation explains many counting recurrences.

Example: Climbing Stairs

Suppose:

You may climb
1 or 2 steps.

Question:

How many ways
can you reach step n?

State:

$$ dp[i] $$

Meaning:

number of ways
to reach step i

To arrive at:

$$ i $$

the previous step must be:

$$ i-1 $$

or:

$$ i-2 $$

Therefore:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Base cases:

$$ dp[0]=1 $$

$$ dp[1]=1 $$

This is the classic Fibonacci recurrence.

The key observation:

Counts from independent transitions are added together.

Why Addition Appears

Suppose:

100 ways
reach state A

50 ways
reach state B

If every solution reaching A can continue to the target, and every solution reaching B can continue independently, then:

total ways
=
100 + 50

Counting DP almost always follows this principle.

Independent sources of solutions contribute additively.

Example: Grid Paths

Consider an (m \times n) grid.

Allowed moves:

right

down

State:

$$ dp[i][j] $$

Meaning:

number of paths
to cell (i,j)

Every path arrives from:

• above
• left

Recurrence:

$$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$

Base conditions:

$$ dp[0][j]=1 $$

$$ dp[i][0]=1 $$

The recurrence mirrors the physical structure of the problem.

Example: Coin Change Counting

Given coins:

1
2
5

Question:

How many ways
can amount n
be formed?

State:

$$ dp[x] $$

Meaning:

number of ways
to create amount x

Transition:

$$ dp[x] += dp[x-coin] $$

Implementation:

dp[0] = 1

for _, coin := range coins {

    for amount := coin;
        amount <= target;
        amount++ {

        dp[amount] +=
            dp[amount-coin]
    }
}

Notice:

+=

rather than:

min
max

The goal is accumulation, not optimization.

Order Matters Versus Order Does Not Matter

This distinction is one of the most important concepts in counting DP.

Consider:

coins = {1,2}
target = 3

Order Matters

Valid solutions:

1+1+1

1+2

2+1

Count:

3

Order Does Not Matter

Valid solutions:

1+1+1

1+2

Count:

2

The recurrence may appear similar, but the iteration order changes the interpretation dramatically.

Many counting bugs originate from confusing these two situations.

Example: Counting Subsequences

Given:

ABCABC

Question:

How many subsequences
equal ABC?

State:

$$ dp[i][j] $$

Meaning:

number of ways
first j characters
of target
appear within
first i characters
of source

Suppose:

source[i-1]
=
target[j-1]

Then:

use character

or

skip character

Recurrence:

$$ dp[i][j] = dp[i-1][j] + dp[i-1][j-1] $$

Otherwise:

$$ dp[i][j] = dp[i-1][j] $$

This pattern appears frequently in string counting problems.

Example: Partition Counting

Question:

How many ways
can integer n
be written as a sum?

Example:

4

4

3+1

2+2

2+1+1

1+1+1+1

Answer:

5

A suitable state may track:

remaining value

largest allowable part

This leads naturally to a two-dimensional counting DP.

Many combinatorial counting problems share this structure.

Counting Paths in Directed Acyclic Graphs

Given a DAG:

count paths
from source
to destination

State:

$$ dp[u] $$

Meaning:

number of paths
from node u
to destination

Recurrence:

$$ dp[u] = \sum dp[v] $$

for every outgoing edge:

$$ u \rightarrow v $$

This resembles subtree counting and path aggregation in trees.

The absence of cycles makes dynamic programming possible.

Counting Versus Probability

Probability DP and counting DP often look similar.

Counting:

$$ dp[state] = \sum dp[next] $$

Probability:

$$ dp[state] = \sum p_i \times dp[next_i] $$

The difference is the weighting factor.

Probability distributes fractional mass.

Counting accumulates integer counts.

Understanding this distinction prevents many modeling errors.

Large Numbers

Counting problems frequently produce enormous answers.

Consider:

number of subsets
of 100 elements

Result:

$$ 2^{100} $$

which greatly exceeds standard integer limits.

Common approaches include:

Arbitrary Precision Arithmetic

Use big integers.

Modular Arithmetic

Compute:

$$ answer \bmod M $$

where:

$$ M = 10^9+7 $$

or another prime modulus.

Many contest problems require modular counting.

Modular Counting DP

Recurrence:

$$ dp[i] = (dp[i-1] + dp[i-2]) \bmod M $$

Implementation:

dp[i] =
(
    dp[i-1]
    +
    dp[i-2]
) % MOD

Apply the modulus at every update.

Waiting until the end often causes overflow.

Inclusion-Exclusion and Counting DP

Some counting problems involve overlapping solution sets.

Example:

count valid schedules

where multiple constraints interact.

Dynamic programming may count configurations while inclusion-exclusion removes duplicates.

The two techniques often appear together in advanced combinatorial problems.

Common Counting Patterns

Several state designs appear repeatedly.

Path Counting

$$ dp[node] $$

Examples:

• DAG paths
• grid paths
• maze traversal

Sequence Counting

$$ dp[i] $$

Examples:

• staircase problems
• compositions
• partitions

Subsequence Counting

$$ dp[i][j] $$

Examples:

• pattern matching
• string analysis

Subset Counting

$$ dp[mask] $$

Examples:

• set partitions
• assignment counting
• combinatorial enumeration

Avoiding Double Counting

The most common counting error is counting the same solution multiple times.

Example:

1+2

2+1

Should these be considered different?

The answer depends on the problem statement.

Always determine:

Does order matter?

before designing the recurrence.

A correct recurrence with the wrong interpretation can produce completely incorrect counts.

Common Mistakes

Using Maximum Instead of Addition

Optimization recurrences frequently use:

max

Counting recurrences almost always use:

+

Switching between the two accidentally is common.

Incorrect Base Cases

For counting:

$$ dp[0]=1 $$

often means:

one way
to do nothing

This interpretation is subtle but essential.

Overflow

Counts grow rapidly.

Use appropriate numeric types or modular arithmetic.

Double Counting

Different transitions may generate identical solutions.

Verify that every valid solution is counted exactly once.

Missing States

Counting DP must account for every valid construction path.

Incomplete state definitions silently lose solutions.

Recognizing Counting DP

Strong indicators include:

how many ways

count configurations

number of paths

number of sequences

number of arrangements

count valid solutions

Whenever the output is a count rather than an optimum, counting DP should be considered.

Complexity Analysis

Let:

$$ S $$

be the number of states.

Let:

$$ K $$

be the number of transitions per state.

Time complexity:

$$ O(SK) $$

Memory:

$$ O(S) $$

The asymptotic complexity often matches optimization DP.

Only the aggregation operation changes.

Takeaway

Counting dynamic programming replaces optimization with enumeration. Instead of finding the best solution, each state records the number of valid ways to construct that state. Independent sources of solutions contribute additively, leading to recurrences built around summation rather than minimization or maximization. From path counting and subsequence counting to partitions and combinatorial enumeration, counting DP provides a systematic framework for solving problems whose brute-force solution space may be exponentially large while still producing answers in polynomial time.