2 ms·
> Elevating "memoization+recursion" to "dynamic programming" seems like a development that Bellman didn't anticipate Well, it also isn't a development that hap
by thaumasiotes 1y ago
> Elevating "memoization+recursion" to "dynamic programming" seems like a development that Bellman didn't anticipate
Well, it also isn't a development that happened. You can (always) implement dynamic programming as recursion with memoization. But an algorithm that is recursive and memoized isn't necessarily an example of dynamic programming.
The point of dynamic programming is that you set up the recursion so that recursive calls do hit the cache, not that there is a cache and if you're lucky they might hit it.
- zelphirkalt 1y agoUsually though when using recursion to solve an algorithmic problem, people memoize results they know will be needed later again. So in most cases that should automatically become the same thing in practice.