liveBook · Manning

State

As explained in Timeless Algorithms, The Foundational Ideas

A representation of a problem configuration that captures information needed to determine subsequent choices and outcomes.

In dynamic programming, a state identifies a subproblem by retaining the information needed to distinguish it from others. A recurrence specifies how subproblems depend on smaller ones; transitions connect states, and base cases anchor their evaluation. section 6.1.3 section 6.2.3

The state must be neither too sparse nor unnecessarily detailed: missing information can merge distinct subproblems and yield incorrect results, while extra information can increase computation and memory. Its form depends on the problem. Knapsack uses item count and remaining capacity; coin change uses the target amount; inventory planning tracks period and stock; network routing tracks endpoints and permitted intermediate nodes. section 6.1.3 section 6.2.3 section 6.3.3 section 6.4.2

ways[0]=1

For coin change, ways[0]=1 is the base value from which counts for larger amounts can be built. section 6.3.3

“State” also describes different things in other settings. In medical decisions, disease present or absent are possible states of the world, whose probabilities and consequences inform the choice to treat. In recurrent neural networks, an internal state carries information forward through a sequence; transformers instead let tokens evaluate relationships directly rather than relying entirely on that intermediate state. section 7.1 section 13.4.2

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Works through state definitions, transitions, and base cases across problems, showing that formulations depend on the task.
Examples
Uses item count and capacity in knapsack, and target amount in coin change, to illustrate alternative state representations.
What you can do after
Apply dynamic programming by specifying states, transitions, and base cases for a problem.
How it connects
Connects dynamic-programming states to recurrence relations, transitions, and base cases, and distinguishes them from recurrent neural-network state.

Also explained in

Compare how 52 books explain state →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.