Dynamic Programming Through Memoization
Luckily, we do have options, and that is through something called dynamic programming. Dynamic programming is the process of optimizing recursive problems that have overlapping subproblems.
(Don’t pay too much attention to the word dynamic. There’s some debate about how the term came about, and there’s nothing obviously dynamic about the techniques I’m about to demonstrate.)
Optimizing an algorithm with dynamic programming is typically accomplished with one of two techniques.
The first technique is something called memoization. And no, that’s not a typo. Pronounced meh-moe-ih-ZAY-shun, memoization is a simple, but brilliant, technique for reducing recursive calls in cases of overlapping subproblems.
Get A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
