State is the information needed to describe one point in a computation. It answers the question: “What must the algorithm know to continue correctly from here?”
State appears in search, dynamic programming, graph traversal, simulations, and recursion.
Core Idea
A good state includes enough information to make the next decision, but not more than necessary. If the state is missing important information, the algorithm may merge situations that should be different. If the state includes too much information, the algorithm may become unnecessarily large.
In dynamic programming, choosing the right state is often the main difficulty.
Python Example
from collections import deque
start = (0, 0)
queue = deque([start])
visited = {start}For a grid search, (row, col) can be the state because it describes the current position.
Common Confusions
State is not always just the current value. A path problem might need current node, remaining fuel, used keys, or visited items.
Two states can have the same visible position but different future possibilities. If those possibilities differ, the states must be represented differently.
When To Use It
Use explicit state reasoning when designing BFS, DFS, dynamic programming, backtracking, or any algorithm where “where we are” includes more than one piece of information.