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
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



















































