Space Optimization

If each state only depends on a small window of previous states, you don’t need the full table. Keep only the dependencies.