NOTE
Dynamic Programming
Solving overlapping subproblems with memoization/tabulation by defining state, transition, initialization, and answer.
This is a historical learning note and may contain outdated or incomplete understanding.
Dynamic programming applies when a problem has reusable overlapping subproblems and an optimal/counting structure expressible through smaller states.
A reliable workflow is:
- define the state precisely;
- derive the transition/recurrence;
- establish base cases and evaluation order;
- compute the requested result;
- optimize dimensions only after correctness is clear.
Top-down memoization and bottom-up tabulation are two implementations of the same state-dependency idea.