DSA Notes

Math

Counting with DP

Count the ways with a DP, and speed up range sums with prefix sums.

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.
Watch it run

Try your own input

Practise on LeetCode