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
  1. STATE — what one cell of the table means, written as a sentence.
  2. TRANSITION — how a cell is computed from cells with smaller indices. The recurrence.
  3. 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
MemoisationTabulation
Write it asthe recurrence, directlya loop
Computesonly states neededevery state
Fill orderthe call stack handles ityou choose it
Depth limit~1,000 framesnone
Space optimisationawkwardeasy
Debuggingprint on cache missprint 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 + prev2

26. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Dynamic Programming