In dynamic programming, problem formulation turns a multi-stage optimization task into connected stages: it identifies what information matters at each stage and how decisions affect what follows. section 6.1
A usable formulation specifies:
- The state information retained at each stage. section 6.1
- The decisions and transitions connecting stages. section 6.1
- A recurrence and base cases that let partial solutions combine into a complete result. section 6.1.5
Knapsack and coin change
These optimization problems use the same dynamic-programming framework in different settings; knapsack illustrates constrained resource allocation. section 6.1.5
Formulation is useful when the problem has overlapping subproblems and optimal substructure. Without the right structure, dynamic programming can add complexity without reward. section 6.1 section 6.1.5







