DSA Notes

Dynamic Programming

Advanced DP III

When the direct DP is too big, shrink the state or rewrite the objective.

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

Try your own input

Practise on LeetCode