Dynamic Programming: The SRBOT Recipe

The previous lesson showed 0/1 knapsack defeats greedy because taking an item permanently consumes capacity in a way that can't be undone or exchanged. Dynamic programming (DP) is the paradigm built exactly for this situation: problems with overlapping subproblems (unlike divide-and-conquer's independent ones) and optimal substructure, solved by computing each distinct subproblem's answer exactly once and reusing it. This note gives a concrete, repeatable recipe — SRBOT: Subproblem, Recurrence, Base cases, Order of evaluation, Top-down vs. bottom-up — and works it in full on the classic rod-cutting problem, already having previewed the recurrence style in Floyd-Warshall.