> For the complete documentation index, see [llms.txt](https://interviews.woojiahao.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://interviews.woojiahao.com/problems-guide/dynamic-programming-roadmap/linear-sequence.md).

# Linear Sequence

In general, the problems under this category fall under a similar problem scope as [Perfect Squares](/problems-guide/dynamic-programming-roadmap/warmup/perfect-squares.md) where the optimal answer can usually acquired by solving for every prefix/suffix of the array and then using the previously computed past states to compute the current state.

This is a combination of the trick to "re-frame the problem" and the recurrence pattern of "past states".