Count or sum integers by processing their numerical digits and merging prefixes that have the same possible continuations. Typical state records include the current position, whether the prefix still equals an upper limit, a remainder, or a bit mask of digits already used. The final answer comes from accepting exactly those states satisfying the desired digit constraints.
Binary digit dynamic programming counts or optimizes integers by processing their base-two digits while recording a finite state. A usual state includes the current digit position, whether the prefix still equals the upper bound's prefix, and whatever automaton or arithmetic information controls future digits.
To count without consecutive one bits, retain the previous bit and reject a new one after a one. A tight prefix may use only digits no larger than the corresponding bit of ; a smaller prefix may use either bit thereafter. Leading zeros allow equal-length representations, but properties involving the first nonzero digit may require an additional started flag.
Articles by others on the same topic
There are currently no matching articles.