In dynamic programming, a transition links a state to the smaller states or updated counts used to compute it. It makes the relationship in a recurrence explicit: states identify subproblems, while transitions specify how those subproblems connect. section 6.1.3
Two formulations show how transitions work:
- In 0/1 knapsack, state V(i, c) branches to V(i − 1, c) when item i is excluded, or to V(i − 1, c − wᵢ) when it is included. section 6.2.3
- In coin change, when denomination c contributes to amount n, add ways[n − c] to ways[n]; counts for smaller amounts build counts for larger ones. section 6.3.3
