March 24
Dynamic Programming
What dynamic programming means, when storing subresults avoids an explosion of work, and why the name is scarier than the idea.
What it is
Dynamic programming, or DP, means storing and reusing answers to subproblems so you do not compute everything again.
The name sounds more complicated than the idea.
A lot of the time it is just:
“I already solved this smaller part, so I should not solve it again.”
When to use it
It appears when two things happen together:
- subproblems overlap
- the larger answer depends on those smaller answers
Common mistake
The classic mistake is memorizing a table without understanding where the state came from.
If you do not know what the state represents, the technique becomes ritual.
Better question
Before using it, ask:
- what is the smallest repeated decision here?
- what do I need to remember to avoid recomputation?
- am I thinking in terms of state and transition, or only filling a table?
Share this page
Copy the link manually from the field below.