Frontier dynamic programming Created 2026-10-20 Updated 2026-11-05
Frontier dynamic programming processes a graph or grid in an order and remembers only the processed vertices that still meet unprocessed edges, together with the information needed across that frontier. Its complexity is controlled by frontier width rather than merely by the total vertex count.
For counting paths on a strip, the state may need both vertex degrees and which frontier endpoints are connected through the processed region. Two configurations with the same occupied frontier vertices can differ in whether the next edge closes a forbidden cycle. Recording a canonical connectivity partition prevents this loss of information. This is a graph-oriented form of state compression and transfer dynamic programming.
Transfer dynamic programming Created 2026-10-20 Updated 2026-11-05
Transfer dynamic programming advances through repeated layers while storing a state on their interface. If counts partial configurations with boundary state , transitions give . With identical layers this is repeated multiplication by a transfer matrix.
For binary strings with no consecutive ones, store whether the last digit is zero or one. Appending a zero is allowed from either state; appending a one is allowed only from the zero state. The resulting two-state recurrence gives Fibonacci numbers. The state must retain all information that a later layer can detect, including connectivity when local occupancies alone do not suffice.