State

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.

State is a boundary around relevant memory. It separates what affects the future from what is only history. Two situations can share one state only if every future decision and answer from that point is the same.

Usage Contract

A state representation must include every piece of information that can affect future choices. For a plain grid search, (row, col) may be enough. For a grid with keys, (row, col, keys_mask) may be required.

The contract is not a Python type alone. It is the promise that two computations with the same state have the same future possibilities and the same answer from that point onward.

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.

When Position Is Not Enough

Sometimes the same position can have different futures. Suppose a grid has locked doors and keys. Being at (row, col) with key A is different from being at (row, col) without key A.

The state may need to include the key set:

state = (row, col, keys_mask)

If the visited set stores only (row, col), the algorithm may incorrectly discard a better situation that reaches the same cell with more keys.

State in Dynamic Programming

For a DP table, the state defines what each entry means:

dp[i][capacity]

This might mean “the best value using the first i items with this remaining capacity.” Without that exact sentence, the recurrence is hard to reason about.

A Practical Check

After choosing a state, ask whether two computations with the same state should always produce the same answer. If not, the state is missing information.

Then ask whether any part of the state can be removed without changing future possibilities. If yes, the state may be too large.

Complexity Comes From State Count

For many search and dynamic programming algorithms, the time cost is roughly:

number of reachable states * work per state

If a grid has rows * cols possible positions, plain BFS has at most that many position states. If the state also includes a keys_mask with 2^k possible key sets, the possible state count can grow to rows * cols * 2^k.

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.

On the other hand, including unnecessary history can make the algorithm explode. The goal is not to store everything. The goal is to store exactly what future choices need.

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.

When an algorithm gives wrong answers, ask whether two different situations were accidentally treated as the same state.

The Main Point

State is the information needed to continue correctly. A state that is too small merges different futures; a state that is too large makes the algorithm unnecessarily expensive.