Binary digit dynamic programming (source code)

= Binary digit dynamic programming

= Binary digit DP
{synonym}

<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 $0\leq x\leq N$ 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 $N$; 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.