Exponentiation on States

Treat DP vector as state; linear transform via matrix multiply per step.

Try this in Python

k = 3
vec = [1, 0, 0]
T = [[1, 1, 0], [1, 0, 0], [0, 0, 1]]
# one step: new = T * vec (toy sizes)
print(len(vec), len(T))

Key takeaways

• Dimension is recurrence width—keep small.
• Exponentiate transform, not naive simulation for huge steps.
• Sparse transitions use graph exponent tricks instead.