DYNAMIC PROGRAMMING › FOUNDATIONS

Transition Relation

Once the state is defined, the transition tells you how to move from smaller solved states to the current answer.

Time

O(1)

Space

O(1)

Key Principle 1

Write the recurrence by asking what choice is made at each step.

Key Principle 2

Every transition should depend only on already solved subproblems.

Key Principle 3

Most DP recurrences are built from take, skip, extend, or split decisions.

Key Principle 4

A clean transition is what turns recursion into tabulation.

Loading Lab...