3 ms·
I have a question about the dynamic programming bit. These questions do not seem intuitive unless its one of the simple ones like, add or multiply the two pre
by drenvuk 9y ago
I have a question about the dynamic programming bit. These questions do not seem intuitive unless its one of the simple ones like, add or multiply the two previous values in the memo (fibonacci) or just check the min or max of the value and modify regarding that. Those patterns can sometimes be easy to spot.
The more difficult ones feel like you absolutely have to have seen the problem before because there is complex relationship between the sub problems that are used to solve by induction/bottom up. How is someone supposed to solve these? Throwing out tons of guesses at the start feels like it'll still end up with me getting shown out before lunch time.
Recursion and memoization is easy but dynamic programming doesn't really feel as natural. Ways to get better? Just do more?
- 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.
- gaylemcd 9y agoBasically, yes, do more. If you want to flip a memoization problem into bottom-up dynamic programming: 1. Make sure you really understand the memoization approach 2. Look at the base cases. What are the very last things the recursive approach does? 3. Build up the next case from the base case. 4. Repeat