Course contentsShow
← Computer Science
Lesson 920 of 2,87222. Dynamic ProgrammingFree lesson

State Definition and Transitions

Define what constitutes a state in a DP solution and how to express transitions between states.

State Definition and Transitions

You'll learn: How to define states in dynamic programming and describe the rules for moving between them.

What is a State?

In dynamic programming, a state is a snapshot of the problem at a specific point. Think of it like a save point in a video game—it captures just enough information to know where you are and what decisions remain.

A state typically consists of one or more variables that describe:

  • Where you are in the input (e.g., index in an array)
  • What constraints are currently active (e.g., remaining capacity)
  • The subproblem you're solving

For example, in the classic "climbing stairs" problem where you can take 1 or 2 steps, the state is simply n (the number of stairs remaining).

State Transitions

A transition is the rule for moving from one state to another. It describes how the answer to your current subproblem depends on answers to smaller subproblems.

Think of transitions as bridges between save points. They answer: "If I make this choice now, which state(s) do I move to?"

In the stairs problem:

  • State n transitions to states n-1 (take 1 step) and n-2 (take 2 steps)
  • The transition rule: ways(n) = ways(n-1) + ways(n-2)

Why This Matters

Defining states clearly determines your DP table structure. Identifying transitions gives you the recurrence relation—the mathematical formula that solves your problem.

Bad state definitions include redundant information or miss crucial details. Good state definitions are minimal yet complete.

Key Takeaway: A DP state captures "where you are" in the problem, and transitions define "how you got here" or "where you can go"—together they form the blueprint for your solution.