364. How do you turn a recursive recurrence into memoised code, and when does it help?
EasyDynamic programming
Show model answer
Identify the state (the parameters that fully determine a subproblem's answer), write the recursive function directly from the recurrence, and add a cache keyed by the state: check it before computing and store the result after. Running time becomes (number of distinct states) × (work per state, excluding recursive calls). Space is the cache plus the recursion depth.
Memoisation only helps when subproblems overlap. Naive Fibonacci makes about φ^n calls, but with a cache it makes O(n) calls. Merge sort's subproblems never repeat, so caching gains nothing. Watch out for hidden state, such as a global variable or a mutable list the function reads, which must become part of the cache key or the memo returns wrong answers.