Re:What I've learned from 100s of interviews with candidates...
by sanjoy_das on Wednesday May 24, 2017 @04:44PM
(#14413305)
> 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.
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.