TechniqueLessonSoftware engineeringDecision-making
In dynamic programming the hard part is finding the subproblem, not the memoisation
Reducible · 5 Simple Steps for Solving Dynamic Programming Problems
The idea
Candidates learn dynamic programming as a technique for caching results, and then fail the problems because caching was never the difficulty. Reducible's approach starts earlier: find the subproblem, the smaller version of the question whose answer the larger one is built from, and the relationship between subproblems, before touching an implementation. Once the recurrence is written down, memoisation is mechanical. The lesson transfers beyond coding interviews. Most hard problems are hard because the decomposition is not obvious, and the work is in finding the structure rather than in executing on it.
Find the subproblem and the recurrence first; the implementation is mechanical once the structure is clear.
When it works
Coding interviews, and any problem whose difficulty is in the decomposition.
When it may fail
Not every problem has a clean recurrence, and recognising which pattern applies is itself a skill that needs practice across many problems. The method helps once you have guessed the pattern.
How to use it
On a dynamic programming question, spend the first minutes saying out loud what a smaller version of the problem looks like and how the answer to it feeds the full one. Write the recurrence on the whiteboard before any code.
Where it came from
Video 5 Simple Steps for Solving Dynamic Programming Problems · Reducible
What the source says. Reducible finds the subproblem and the relationship between subproblems before touching an implementation.
Connected ideas
Says something similar
An index turns a table scan into a handful of page reads, paid for in write speed and diskAn index buys read speed with write speed and disk; add one for the query you run most and remove the ones you never use.
Concepts
Put it to work on L3VLUP
More like this
- Post-mortemFounders and companiesDocumentary
A board that accepts a narrative has stopped doing diligence
A compelling story is a claim to test, and the test for a technology is watching it work.
From The Inventor: Out for Blood in Silicon Valley · 2019
- FrameworkInvestingFilm
A cheap measurable signal beats an expensive intuitive one at scale
The market misprices what is hard to measure, so a consistent cheap signal can beat an expensive expert.
From Moneyball · 2011
- Decision principleDecision-makingBook
A good decision and a good outcome are separate things
Judge a decision by what was knowable when it was made, and keep the outcome in a separate column.
From Thinking in Bets · Annie Duke
- TechniqueProductVideo located
A metrics question is a structured hunt: north star, guardrails, then the segment
Clarify the metric, protect the guardrails, then decompose the drop by segment until it is isolated; show the process, not a guess.
From Google Product Manager Metrics Interview: A Worked Mock · Aakash Gupta