The idea
Always multiply states by transition cost first. If the product is too large, the DP needs to change, not the constant factor.
Ways to shrink it: drop a dimension that can be computed from the others, cap a dimension with an observation (beyond some value the answer is the same), or replace a long history by the few numbers the rules actually look at.
Ways to rewrite the objective: an absolute value is a choice of sign, |x| = max(x, −x), so a sum of absolute values becomes “pick a sign for each term”, which a DP can do term by term.
Sample problem
552. Student Attendance Record II ↗ Hard
An attendance record is a string of P (present), A (absent) and L (late). It earns an award if it has fewer than 2 absences and never 3 late days in a row. Count the award-winning records of length n, modulo 10⁹+7.
n = 3 output = 19
Why the solution works
There are 3ⁿ records, far too many to list for n = 100 000. A DP that remembers the whole record so far is no better.
Shrink the state to what the rules actually look at. To know whether the next character is allowed, you need only the number of absences so far and the length of the current run of late days. That is 2 × 3 = 6 states, whatever n is.
Each day every state passes its count on to the states reached by adding P, A or L. The answer is the sum of the six counts after n days.
Complexity: O(n) time with a constant of 6 states × 3 moves, O(1) memory.
Watch out
- Check that the rewritten objective has the same optimum: choosing signs freely can never beat the true absolute values, and the true signs are among the choices.
- Neighbouring coefficients must be consistent with one sign per difference; encode that in which t′ may precede t.
- An early exit (for example, “enough resources to cover everything”) often removes the largest inputs.