DYNAMIC PROGRAMMING › FOUNDATIONS

State Definition

The first DP decision is the most important one: define exactly what your state represents before you write the recurrence.

Time

O(1)

Space

O(1)

Key Principle 1

A state must contain everything needed to solve the current subproblem.

Key Principle 2

Good states are usually compact, stable, and easy to transition from.

Key Principle 3

Index-based states work well for arrays, strings, and prefix problems.

Key Principle 4

If the state is unclear, the rest of the DP solution usually becomes messy.

Loading Lab...