Transfer dynamic programming
ID: transfer-dynamic-programming
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.
New to topics? Read the docs here!