The hardest part is the state
Dynamic programming solves a problem by breaking it into subproblems whose answers combine into the whole. The crux is rarely the arithmetic. It is choosing the state, the set of variables that uniquely identifies a subproblem, so that overlapping work is computed once and reused.
What makes a good state
A state must capture everything that affects the remaining answer and nothing that does not.
- It should be sufficient, meaning two situations with the same state always have the same future answer.
- It should be minimal, because every extra dimension multiplies the table size.
- It must support a transition, a recurrence that builds a state from smaller ones.
For a knapsack, the state is the item index and the remaining capacity. For edit distance, it is two string positions. Naming these variables is the design act that everything else follows.
Order, base cases, and memory
Once the state and transition exist, you choose an evaluation order so each state is ready before it is needed, set base cases for the smallest subproblems, and optionally shrink memory by keeping only the rows the recurrence still references.
Key idea
Dynamic programming succeeds or fails on state design: pick variables that are sufficient and minimal, define a transition between them, and overlapping subproblems collapse into reusable answers.