Lesson 28.2 · DP Foundations: 1D
Tabulation and the Five-Step Recipe
Bottom-up DP fills a table from the smallest states upward. Write down state, transition, base cases, order and answer before coding.
14 min
Think of it like this
Climbing a staircase and chalking on each step the number of ways to reach it. Each step's number is the sum of the two steps below, so you just walk up writing numbers.
1.The recipe
1. State: what does dp[i] mean, in words? ("ways to reach step i"). 2. Transition: how does dp[i] come from smaller states? (dp[i] = dp[i − 1] + dp[i − 2]). 3. Base cases: the smallest states (dp[0] = 1, dp[1] = 1). 4. Order: fill so every needed state is ready (left to right). 5. Answer: which cell? (dp[n]).
Tabulation avoids recursion depth limits and often lets you shrink memory: if dp[i] only uses the last two cells, keep two variables instead of an array.
n = 5Step 1/5Base cases: 1 way to stand at step 0, 1 way to reach step 1.
Remember
- State → transition → base → order → answer.
- Bottom-up has no recursion limit.
- Keep only the cells the transition reads.
Common mistakes
- Starting to code before defining dp[i] in words.
- Off-by-one between "first i items" and "index i".