3 ms·
> Recursion and memoization is easy but dynamic programming doesn't really feel as natural. Ways to get better? Just do more? Once you have the recursive solut
by sanjoy_das 9y ago
> Recursion and memoization is easy but dynamic programming doesn't really feel as natural. Ways to get better? Just do more?
Once you have the recursive solution, the DP solution should be fairly easy. Draw out the recursion tree for an example (or do it more generally), convert it to a DAG by combining redundant nodes, and then do a topological sort. That topological sort is the order in which you need to solve the subproblems to get a DP solution.
- samuraijack 9y agoThanks! That is quite intuitive.