Micro-questions over the memoisation and tabulation module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The three declarations
1. What are the three things every dynamic program must name?
Answer
- STATE — what one cell of the table means, written as a sentence.
- TRANSITION — how a cell is computed from cells with smaller indices. The recurrence.
- BASE CASE — the cells filled directly, because nothing smaller builds them.
2. Give all three for climbing stairs.
Answer
STATE: ways[i] = the number of distinct ways to reach step .
TRANSITION: ways[i] = ways[i-1] + ways[i-2] — you arrived from with a 1-step or from with a 2-step, and those are disjoint.
BASE: ways[0] = 1, ways[1] = 1.
3. When should you write those three lines?
Answer
Before writing any code. They are the design; everything after is transcription.
4. What makes the state the hard one?
Answer
Making it a complete sentence. “dp[i] is about index i” is not a state; “dp[i] is the number of ways to reach step i” is. If you cannot finish the sentence, you do not yet have a DP.
B. The vocabulary
5. What is the state space, and what is it the first factor in?
Answer
The set of all subproblems. Its size is the first factor in the complexity.
6. What is the transition’s role in the complexity?
Answer
Its cost is the second factor — complexity is states × transition.
7. What dictates the fill order?
Answer
The transition. Every cell a transition reads must already hold its final value.
8. What is a rolling array?
Answer
Space optimisation — keeping only the last row (or last few cells) of a table, when the transition never reaches further back.
9. What is reconstruction?
Answer
Recovering the actual solution — the path, subset or string — rather than just its value, usually by walking the table backwards from the answer cell.
C. Filling the table
10. What single requirement fixes the fill order?
Answer
Every new cell reads only cells already filled. That is the whole of what “bottom-up” means.
11. Climbing stairs produces Fibonacci numbers. Coincidence?
Answer
No — the recurrence is identical. Climbing stairs is Fibonacci with different base cases, which matters because the same table shape solves problems that sound unrelated.
D. Four implementations
12. Compare operation counts at .
Answer
Naive 2,692,537; memoised 59; tabulated 29; rolling 29. Naive is exponential; the other three are linear.
13. Why is memoisation’s count about and tabulation’s about ?
Answer
Each state is entered once as a miss and once as a hit under memoisation; tabulation has no lookups at all.
14. What is notable about the memoised code?
Answer
The recursion is unchanged from the naive version — three lines were added. That is why memoisation is the right first move: you write the recurrence exactly as you reasoned about it, then cache.
15. Why memo=None rather than memo={}?
Answer
A mutable default shares one dictionary across every call for the lifetime of the process, including calls from unrelated code.
E. Which one to use
16. Give the six-row comparison.
Answer
| Memoisation | Tabulation | |
|---|---|---|
| Write it as | the recurrence, directly | a loop |
| Computes | only states needed | every state |
| Fill order | the call stack handles it | you choose it |
| Depth limit | ~1,000 frames | none |
| Space optimisation | awkward | easy |
| Debugging | print on cache miss | print the table |
17. What happens to memoised vs tabulated at ?
Answer
Memoised raises RecursionError — the recursion depth, not the cache. Tabulated is fine, because it is a loop.
18. State the rule for choosing.
Answer
Sparse state space — you need only a small fraction of reachable states — memoise, because tabulation would compute all of them. Dense, or deeper than ~1,000 — tabulate.
19. What is the practical order of work?
Answer
Write the memoised version first — it is the recurrence you already reasoned about and it is hard to get the order wrong. Convert to tabulation only if you need the depth or the space optimisation.
F. Fill order
20. Tabulate climbing stairs right-to-left. Right answer, wrong answer, or error?
Answer
A wrong answer, silently — 0.
21. Why exactly?
Answer
It computes ways[n] first, which reads ways[n-1] and ways[n-2] — both still zero, because they have not been computed. The zeros propagate. No exception, no warning.
22. State the rule that generates the order for every DP.
Answer
The transition dictates the order — every cell a transition reads must already be final. Read your recurrence, note which indices it reads, choose the loop direction that guarantees those come first.
23. What does memoisation handle automatically here?
Answer
The call stack cannot get the order wrong, because it computes a dependency at the moment it is needed.
G. Cutting the memory
24. Where do most DP tutorials stop, and what is the step after?
Answer
They stop at a working table. The step after is noticing how little of it you still need.
25. Reduce climbing stairs to space. Why is it possible?
Answer
It reads only ways[i-1] and ways[i-2] — never anything further back — so two variables suffice:
prev2, prev1 = 1, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev226. Apply the same move to unique grid paths.
Answer
table[i][j] = table[i-1][j] + table[i][j-1] reads the row above and the cell to the left, never anything higher — so one row suffices, giving instead of .
H. Traps
27. What is the most common failed-DP symptom?
Answer
A state you cannot write as a sentence. It presents as a transition that “almost works”.
28. When is tabulation actively wasteful?
Answer
When the state space is sparse. If only 200 of states are reachable, tabulation does 5,000× the necessary work.
29. When should you optimise space, and why not before?
Answer
After the DP is correct. The rolling array is harder to debug and destroys reconstruction.
30. What are mutually exclusive?
Answer
Space optimisation and reconstruction. Decide which you need before choosing.
31. What must you count first, and why?
Answer
The state space. Complexity is states × transition cost — if that product is too big, no implementation detail rescues it; you need a different state.
32. Summarise the lesson in one sentence.
Answer
Name the state as a sentence, write the transition, fill in the order the transition demands — memoise first, tabulate when you need depth or space.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Memoisation & Tabulation — the module
- What Makes a Problem DP — Question Bank
- Classic 1-D DP — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering