The idea
A counting DP has the same shape as an optimising one, but transitions add the ways of the previous states instead of taking a maximum, and everything is reduced modulo a prime.
The state must describe each configuration exactly once, or it will be counted twice.
When a transition sums a contiguous range of the previous row, prefix sums of that row give the range in O(1), removing a whole factor from the running time.
Sample problem
1155. Number of Dice Rolls With Target Sum ↗ Medium
You roll n dice with k faces each (numbered 1 to k). Count the ways, out of kⁿ, to get a total of exactly `target`, modulo 10⁹+7.
n = 2, k = 6, target = 7 output = 6
Why the solution works
Listing all kⁿ outcomes is hopeless, but outcomes with the same running total are interchangeable: what the remaining dice can do depends only on the total so far.
So count per total. f[s] is the number of ways to reach s with the dice thrown so far. Throwing one more die sends the ways at total s − face to total s, for every face. The ways are added, because different last faces give different outcomes.
It has the shape of an optimisation DP with max replaced by plus, and every addition reduced modulo 10⁹+7.
Complexity: O(n · target · k) time, O(target) memory.
Watch out
- Add MOD before the remainder after subtracting two prefix sums.
- Reduce at every step; a single unreduced product can overflow.
- Loop order decides whether orderings are counted separately: items outside, totals inside counts combinations.